题意:
分析:
每个人按照 AC数目 为第一关键字降序,罚时 为第二关键字升序 的排序方式,动态修改,查询排名
这个修改和查询很平衡树,所以我们就上 \(fhq\) ,将值的大小当做键值,所以我们需要新建一个结构体,然后重载 \(<=\) 号,剩下操作和普通 \(fhq\) 一毛一样
代码:
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
using namespace std;
namespace zzc
{
typedef unsigned int ui ;
inline ui read()
{
ui x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e6+5;
ui t,n,m,seed,lst=7;
ui randNum( ui& seed , ui last , const ui m)
{
seed = seed * 17 + last ; return seed % m + 1;
}
namespace fhq_treap
{
struct node
{
int num,tim;
node(){}
node(int num,int tim):num(num),tim(tim){}
bool operator <=(const node &b)const
{
return num==b.num?tim<=b.tim:num>b.num;
}
}w[maxn],val[maxn];
int siz[maxn],son[maxn][2],rnd[maxn];
int cnt,rt;
void clear()
{
for(int i=1;i<=cnt;i++) son[i][0]=son[i][1]=siz[i]=0,val[i]=node(0,0);
cnt=rt=0;
}
void pushup(int rt)
{
siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
}
int new_node(node x)
{
int u=++cnt;
val[u]=x;siz[u]=1;
rnd[u]=rand();
return u;
}
void split(int tmp,node 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(node k)
{
int x,y,z;
node 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(node k)
{
int x,y;
split(rt,k,x,y);
rt=merge(x,merge(new_node(k),y));
}
ui query(node k)
{
int x,y;k.tim--;
split(rt,k,x,y);
ui res=siz[x];
rt=merge(x,y);
return res;
}
}
using namespace fhq_treap;
void work()
{
t=read();
while(t--)
{
ui a,b;
clear();
m=read();n=read();seed=read();
for(ui 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]);
printf("%u\n",lst);
}
for(ui j=1;j<=m;j++) w[j]=node(0,0);
}
}
}
int main()
{
zzc::work();
return 0;
}