本文共 1909 字，大约阅读时间需要 6 分钟。
要求维护一个二维权值的集合并支持单点修改，用平衡树维护即可。
因为$n\le 10^6$但$m\le 10^5$，所以最多只有$10^5$个人被操作。
记录每个人的二维权值，只维护被操作过的人权值的平衡树即可。
如果一开始将$10^6$个人都建出来会$TLE$。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef unsigned int ui;int ls[100010];int rs[100010];int r[100010];int v[100010];int t[100010];int size[100010];int cnt;int m,T;ui seed;int x,y;int a,b,c;ui last=7;ui n;int ac[1000010];int tim[1000010];int root;ui randNum(ui& seed,ui last,const ui m) { seed=seed*17+last; return seed%m+1;}inline void init(){ cnt=root=0; memset(ac,0,sizeof(ac)); memset(tim,0,sizeof(tim));}inline int build(int val){ int rt=++cnt; r[rt]=rand(); v[rt]=1; t[rt]=val; size[rt]=1; ls[rt]=rs[rt]=0; return rt;}inline void pushup(int rt){ size[rt]=size[ls[rt]]+size[rs[rt]]+1;}inline int merge(int x,int y){ if(!x||!y) { return x+y; } if(r[x] =tim)) { y=rt; split(ls[rt],x,ls[y],ac,tim); pushup(y); } else { x=rt; split(rs[rt],rs[x],y,ac,tim); pushup(x); }}inline void split2(int rt,int &x,int &y,int k){ if(!rt) { x=y=0; return ; } if(size[ls[rt]]>=k) { y=rt; split2(ls[rt],x,ls[y],k); pushup(y); } else { x=rt; split2(rs[rt],rs[x],y,k-size[ls[rt]]-1); pushup(x); }}inline void solve(){ scanf("%u%d%u",&n,&m,&seed); for(int i=1;i<=m;i++) { x=randNum(seed,last,n); y=randNum(seed,last,n); if(!ac[x]) { ac[x]++; tim[x]+=y; int now=build(tim[x]); split(root,a,b,ac[x],tim[x]); root=merge(a,merge(now,b)); } else { split(root,a,b,ac[x],tim[x]); split2(b,b,c,1); v[b]++; t[b]+=y; root=merge(a,c); split(root,a,c,v[b],t[b]); root=merge(merge(a,b),c); ac[x]++; tim[x]+=y; } split(root,a,b,ac[x],tim[x]); last=size[a]; printf("%d\n",last); root=merge(a,b); }}int main(){ scanf("%d",&T); while(T--) { init(); solve(); }}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10826676.html