题目
分析
平衡树模板题。查询一个数的排名。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
namespace STD{
const int N=1e6+5;
unsigned int t,n,m,seed,lst=7;
unsigned int randNum(unsigned int& seed , int last , const int m){
seed = seed * 17 + last ; return seed % m + 1;
}
namespace FHQTreap{
struct Change{
int num,tim;
Change(){}
Change(int num,int tim):num(num),tim(tim){}
bool operator <=(const Change &b)const{
return num==b.num?tim<=b.tim:num>b.num;
}
}w[N],val[N];
int siz[N],son[N][2],rnd[N];
int cnt,rt;
void clear(){for(int i=1;i<=cnt;i++) son[i][0]=son[i][1]=siz[i]=0,val[i]=Change(0,0);cnt=rt=0;}
void pushup(int rt){siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;}
int NewNode(Change x){int u=++cnt;val[u]=x;siz[u]=1;rnd[u]=rand();return u;}
void split(int tmp,Change x,int &u,int &v){
if(!tmp){u=0;v=0;return ;}
if(val[tmp]<=x){u=tmp;split(son[u][1],x,son[u][1],v);pushup(u);}
else{v=tmp;split(son[v][0],x,u,son[v][0]);pushup(v);}
}
int merge(int x,int y){
if(!x||!y) return x|y;
if(rnd[x]<rnd[y]){son[x][1]=merge(son[x][1],y);pushup(x);return x;}
else{son[y][0]=merge(x,son[y][0]);pushup(y);return y;}
}
void del(Change k){
int x,y,z;Change tmp=k;tmp.tim--;
split(rt,k,x,z);split(x,tmp,x,y);
y=merge(son[y][0],son[y][1]);rt=merge(x,merge(y,z));
}
void Insert(Change k){
int x,y;
split(rt,k,x,y);
rt=merge(x,merge(NewNode(k),y));
}
unsigned int Query(Change k){
int x,y;k.tim--;
split(rt,k,x,y);
unsigned int res=siz[x];
rt=merge(x,y);
return res;
}
}
using namespace FHQTreap;
void work(){
read(t);
while(t--){
unsigned int a,b;
clear();read(m),read(n),read(seed);
for(int i=1;i<=n;i++){
a=randNum(seed,lst,m);b=randNum(seed,lst,m);del(w[a]);
w[a].num++;w[a].tim+=b;
Insert(w[a]);lst=Query(w[a]);
write(lst),putchar('
');
}
for(int j=1;j<=m;j++) w[j]=Change(0,0);
}
return ;
}
}
int main(){
STD::work();
return 0;
}