题意简述
有 (n) 次 (AC) ，通过给定函数生成第 (i) 次 (AC) 的人的序号和罚时。
以 (AC) 的题目数为第以关键字排序， (AC) 数相同的罚时短的排在前面。
求每有一次 (AC) 后，这次 (AC) 的人在总排名中排在他前面的有几人（不包括与他罚时、通过题目数都相同的人）。
(n leq 10^6)
想法
显然用平衡树呀！
关键在于选择辣个，鉴于我很懒，所以选了 (FHQtreap)
用树状数组维护通过了 (i) 道题的总人数，用 (FHQtreap) 维护相同 (AC) 数的人的罚时。
出现一次新 (AC) 后，将它从原有的树中 (split) 出去，再加入新的树中。
排名随便算算就好（我太懒了……
总结
(FHQtreap) 有两种 (split) 方式，分别是根据权值、根据大小，是都可以使用的。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000005;
void write(int x){
if(x==0) { putchar('0'); putchar('
'); return; }
if(x<0) putchar('-'),x=-x;
int t=0; char ch[20];
while(x) ch[t++]=x%10+'0',x/=10;
for(;t;) putchar(ch[--t]);
putchar('
');
}
int n,m;
typedef unsigned int ui ;
ui sd,lst;
ui randNum( ui& seed , ui last , const ui m){
seed = seed * 17 + last ; return seed % m + 1;
}
int t[N],num[N];
int c[N];
void add(int x,int y) { while(x<=n) c[x]+=y,x+=x&(-x); }
int sum(int x) {
int ret=0;
while(x) ret+=c[x],x-=x&(-x);
return ret;
}
typedef pair<int,int> Pr;
int val[N],pri[N],ch[N][2],sz[N],cnt;
int rt[N];
void update(int x) { sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]]; }
int merge(int x,int y){
if(!x || !y) return x+y;
if(pri[x]>pri[y]) { ch[x][1]=merge(ch[x][1],y); update(x); return x; }
else{ ch[y][0]=merge(x,ch[y][0]); update(y); return y; }
}
Pr split(int x,int k){//u: val<k v: val>=k
if(!x) return Pr(0,0);
if(val[x]<k) {
Pr y=split(ch[x][1],k);
ch[x][1]=y.first; update(x);
return Pr(x,y.second);
}
else{
Pr y=split(ch[x][0],k);
ch[x][0]=y.second; update(x);
return Pr(y.first,x);
}
}
Pr split_sz(int x,int k){//u: sz<=k
if(!x) return Pr(0,0);
if(sz[ch[x][0]]>=k){
Pr y=split_sz(ch[x][0],k);
ch[x][0]=y.second; update(x);
return Pr(y.first,x);
}
else{
Pr y=split_sz(ch[x][1],k-sz[ch[x][0]]-1);
ch[x][1]=y.first; update(x);
return Pr(x,y.second);
}
}
int find(int id,int k){
Pr y=split(rt[id],k);
Pr x=split_sz(y.second,1);
rt[id]=merge(y.first,x.second);
return x.first;
}
int ins(int id,int x){
Pr y=split(rt[id],val[x]);
int ret=sz[y.first];
rt[id]=merge(y.first,merge(x,y.second));
return ret;
}
int rr;
int rnd() { return rr=1ll*rr*4987657%998244353; }
int main()
{
int T,u,ti,x;
scanf("%d",&T);
lst=7; rr=1;
while(T--){
scanf("%d%d",&m,&n);
scanf("%u",&sd);
for(int i=1;i<=n;i++){
u=randNum(sd,lst,m); ti=randNum(sd,lst,m);
num[u]++; t[u]+=ti;
if(num[u]-1) add(num[u]-1,-1); add(num[u],1);
lst=sum(n)-sum(num[u]);
if(num[u]==1) x=++cnt,val[x]=t[u],pri[x]=rnd(),sz[x]=1;
else x=find(num[u]-1,t[u]-ti),val[x]+=ti;
lst+=ins(num[u],x);
write(lst);
}
//clear
for(int i=0;i<=n;i++) c[i]=0,rt[i]=0;
for(int i=1;i<=m;i++) t[i]=0,num[i]=0;
for(int i=1;i<=cnt;i++) {
val[i]=pri[i]=sz[i]=0;
ch[i][0]=ch[i][1]=0;
}
cnt=0;
}
return 0;
}