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
| #include<bits/stdc++.h>
using namespace std;
int t;
typedef unsigned int ui ;
ui randNum( ui& seed , ui last , const ui m){
seed = seed * 17 + last ; return seed % m + 1;
}
void write(int x)
{
if(x<10)
{
putchar(x+48);
return;
}
write(x/10),write(x%10);
}
int cnt,rt;
struct no{
int siz,pri,ls,rs,ci;
pair<int,int>val;
}tree[2000010];
int new_node(pair<int,int>val,int ci){
tree[++cnt].val=val;
tree[cnt].pri=rand();
tree[cnt].ls=tree[cnt].rs=0;
tree[cnt].siz=ci;
tree[cnt].ci=ci;
return cnt;
}
int cmp(pair<int,int>a,pair<int,int>b){
if(a.first==b.first)return a.second>=b.second;
return a.first<=b.first;
}
void split(int u,pair<int,int> val,int &L,int &R){
if(u==0){
L=R=0;
return;
}
if(cmp(tree[u].val,val)){
L=u;
split(tree[u].rs,val,tree[u].rs,R);
}else{
R=u;
split(tree[u].ls,val,L,tree[u].ls);
}
tree[u].siz=tree[tree[u].ls].siz+tree[tree[u].rs].siz+tree[u].ci;
}
int merge(int l,int r){
if(l==0 or r==0)return l+r;
if(tree[l].pri>tree[r].pri){
tree[l].rs=merge(tree[l].rs,r);
tree[l].siz=tree[tree[l].ls].siz+tree[tree[l].rs].siz+tree[l].ci;
return l;
}else{
tree[r].ls=merge(l,tree[r].ls);
tree[r].siz=tree[tree[r].ls].siz+tree[tree[r].rs].siz+tree[r].ci;
return r;
}
}
int last=7;
int ac[200010],tim[200010];
void solve(){
int m,n;ui seed;
cin>>m>>n>>seed;
cnt=0;rt=0;
memset(tree,0,sizeof tree);
memset(ac,0,sizeof ac);
memset(tim,0,sizeof tim);
rt=merge(rt,new_node({0,0},n));
for(int i=1;i<=n;i++){
int a=randNum(seed,last,m),b=randNum(seed,last,m);
int L,p,R;
split(rt,{ac[a],tim[a]},L,R);
split(L,{ac[a],tim[a]+1},L,p);
ac[a]++;
tim[a]+=b;
tree[p].ci--;
tree[p].siz--;
if(tree[p].ci)rt=merge(merge(L,p),R);
else rt=merge(L,R);
split(rt,{ac[a],tim[a]},L,R);
split(L,{ac[a],tim[a]+1},L,p);
if(p)tree[p].ci++,tree[p].siz++;
else p=new_node({ac[a],tim[a]},1);
write(last=tree[R].siz);
putchar('\n');
rt=merge(merge(L,p),R);
}
}
main(){
freopen("rank.in","r",stdin);
freopen("rank.out","w",stdout);
cin>>t;
while(t--)solve();
return 0;
}
|