Eternity

Until The End

P5338 [TJOI2019]甲苯先生的滚榜

发表于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

巧妙的双关键字平衡树。

题目链接

已知，平衡树维护的是第一关键字的大小顺序，那么，当题目所需的维护信息是二维的话，我们就需要重定义这个大小关系。

即首先比较 $AC$ 数量，然后算罚时。

但是，这样很难实现，而且出锅较多（亲测）。所以，我们可以观察数据。

对于所有数据，保证罚时总和不超过 $1.5\times 10^6$。

那么，我们化双关键字为单关键字，记 $val=(1.5\times 10^6+1)AC-Time$ ，可以知道 $val\leq1.5\times 10^6n=1.5\times 10^{12}$ ，则可以用 long long 维护。

多组数据记得清空，且 seed,m,lastans 需要自然溢出，所以要定义成 unsigned int 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
typedef unsigned int ui ;
ui randNum(ui& seed ,ui last ,const ui m)
{ 
    seed=seed*17+last;
    return seed%m+1; 
}
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e6+10;
int N,Test;
ui M,Seed,lastans=7;
struct B_T
{
    int Idx=0,Rt;
    int x,y,z;
    struct Fhq
    {
        ll val;
        int siz,rd,chi[2];
    }Tr[MAXN];
    #define ls(p) Tr[p].chi[0]
    #define rs(p) Tr[p].chi[1]
    inline void init()
    {
        Idx=Rt=x=y=z=0;
    }
    inline void upDate(int p)
    {
        Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
    }
    inline int newNode(ll val)
    {
        Tr[++Idx]=(Fhq){val,1,rand()};
        return Idx;
    }
    inline void split(int p,ll k,int &u,int &v)
    {
        if(!p) u=v=0;
        else
        {
            if(Tr[p].val<=k) u=p,split(rs(u),k,rs(u),v);
            else v=p,split(ls(v),k,u,ls(v));
            upDate(p);
        }
    }
    inline int merge(int u,int v)
    {
        if(!u||!v) return u+v;
        if(Tr[u].rd<Tr[v].rd)
        {
            rs(u)=merge(rs(u),v);
            upDate(u);return u;
        }
        else
        {
            ls(v)=merge(u,ls(v));
            upDate(v);return v;
        }
    }
    inline void insert(ll v)
    {
        x=y=0;
        split(Rt,v,x,y);
        Rt=merge(merge(x,newNode(v)),y);
    }
    inline void del(ll v)
    {
        x=y=z=0;
        split(Rt,v,x,z),split(x,v-1,x,y);
        y=merge(ls(y),rs(y));
        Rt=merge(merge(x,y),z);
    }
    inline int rank(ll v)
    {
        x=y=0;
        split(Rt,v,x,y);
        int res=Tr[y].siz;
        Rt=merge(x,y);
        return res;
    }
}Tree;
const ll Mul=15e5+1;
ll Val[MAXN];
int main()
{
    // freopen("fhq-treap.in","r",stdin);
    // freopen("fhq-treap.out","w",stdout);
    srand(time(NULL));
    read(Test);
    while(Test--)
    {
        memset(Val,0,sizeof(Val));
        read(M,N,Seed);
        for(ll Ria,Rib;N--;)
        {
            Ria=(ll)randNum(Seed,lastans,M);
            Rib=(ll)randNum(Seed,lastans,M);
            Tree.del(Val[Ria]);
            Val[Ria]+=Mul-Rib;
            Tree.insert(Val[Ria]);
            write(lastans=Tree.rank(Val[Ria])),puts("");
        }
        Tree.init();
    }
    return 0;
}
/*
1
7 3 1
*/
相关文章