新闻详情

P3233 [HNOI2014] 世界树

P5338 [TJOI2019] 甲苯先生的滚榜

相当于修改元素，查询以 AC 数倒序为第一关键字，罚时正序为第二关键字的排名。

修改元素转化为删除再插入，直接上平衡树维护就行。

但注意到数据生成方式相当于随机生成，所以直接用普通 BST 复杂度也是对的。

代码用的还是平衡树。

#include<bits/stdc++.h>
#define N 1100005
using namespace std;
using uint=unsigned;
mt19937 rng(20120412);
uint seed,n,m,lst=7;
struct Data{int AC,tim;bool operator<(const Data &x)const{return AC^x.AC?AC>x.AC:tim<x.tim;}
}a[N];
class FHQ_Treap{private:Data val[N];int rt,idx,p[N],lc[N],rc[N],siz[N];int make(Data x){siz[++idx]=1,val[idx]=x;lc[idx]=rc[idx]=0;return p[idx]=rng(),idx;}void Pushup(int x){siz[x]=siz[lc[x]]+siz[rc[x]]+1;}void split(int x,int &l,int &r,Data v){if(!x) return l=r=0,void();if(v<val[x]) r=x,split(lc[x],l,lc[r],v);else l=x,split(rc[x],rc[l],r,v);Pushup(x);}void merge(int &x,int l,int r){if(!l||!r) return x=l|r,void();if(p[l]<p[r]) x=l,merge(rc[x],rc[l],r);else x=r,merge(lc[x],l,lc[r]);Pushup(x);}public:void clear(){rt=idx=0;}void ins(Data v){int x,y;split(rt,x,y,v),rt=make(v);merge(rt,x,rt),merge(rt,rt,y);}void erase(Data v){int x,y,z;split(rt,x,y,v);split(x,x,z,{v.AC,v.tim-1});merge(z,lc[z],rc[z]);merge(x,x,z),merge(rt,x,y);}int rk(Data v){int res=0;for(int x=rt;x;)val[x]<v?(res+=siz[lc[x]]+1,x=rc[x]):(x=lc[x]);return res;}
}T;
static void get(int &x){x=(seed=seed*17+lst)%m+1;}
static void print(int x){if(!x) return putchar('0'),void();static int Out[8];int top=0;for(;x;x/=10) Out[top++]=x%10;for(;top--;putchar(Out[top]^48));
}
int main(){int Task;scanf("%lld",&Task);for(;Task--;T.clear()){scanf("%u%u%u",&m,&n,&seed);for(int i=1;i<=m;i++)T.ins(a[i]={0,0});for(int A,B;n--;)get(A),get(B),T.erase(a[A]),a[A].AC++,a[A].tim+=B,print(lst=T.rk(a[A])),putchar('\n'),T.ins(a[A]);}return 0;
}