Description
方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:
1.操作格式为1 x y,意味着将编号为z的用户编号改为V,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时1,是一个当前不在排名中的编号。
2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
3.操作格式为3 x,意味着将编号为z的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
4.操作格式为4 k,意味着查询当前排名为足的用户编号,执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:
1 x+a y+a
2 x+a
3 x+a
4 k+a
其中a为上一次操作得到的输出,一开始a=0。
例如:
上一次操作得到的输出是5
这一次操作的输入为:1 13 15
因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10
现在你截获丁方伯伯的所有操作,希望你能给出结果。
Input
输入的第1行包含2个用空格分隔的整数n和m,表示初始用户数和操作数。
此后有m行,每行是一个询问,询问格式如上所示。
Output
输出包含m行。每行包含一个整数,其中第i行的整数表示第i个操作的输出。
Sample Input
10 10
1 2 11
3 13
25
37
28
2 10
2 11
3 14
2 18
4 9
1 2 11
3 13
25
37
28
2 10
2 11
3 14
2 18
4 9
Sample Output
2
2
2
4
3
5
5
7
8
11
2
2
4
3
5
5
7
8
11
HINT
对于 100% 的数据,1 ≤ n ≤ 10^8,1 ≤ m ≤ 10^5
输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 ≤ y ≤ 2 × 10^8,并且y 没有出现在队列中。
对于所有操作 4,保证 1 ≤ k ≤ n。
题解Here!
首先,应该能看出这是一个$Splay$的毒瘤题。
$splay$维护每个用户,再用一个$map$记录每个出现的编号在$Splay$中对应节点。
这个题就做完了
吗?
并不!
因为$n<=10^8$。。。
这玩意好烦啊。。。
我们可以通过构$(kan)$造$(ti)$法$(jie)$得出一种方法:
我们注意到有效询问只有$m<=10^5$个。
也就是说,我们的$Splay$最多只会与$3\times 10^5$个节点有关。
那么我们可以把那些暂时不用的节点全部合并,等到要用的时候再拆点。
这样就可以保证不会$TLE/MLE$了。
然后注意的细节还蛮多的,看代码吧。。。
吐槽:做完这题就会感觉到,维护一个像样的$OJ$真麻烦,尤其是洛谷、LOJ、UOJ等高效的$OJ$,但是$BZOJ$就算了吧。。。
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<map> #define MAXN 1000010 using namespace std; map<int,int> pos; int n,m; int size=0,root=0; struct Splay{ int f,s,son[2]; int l,r; }a[MAXN]; inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } inline void pushup(int rt){ if(!rt)return; a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+a[rt].r-a[rt].l+1; } inline void turn(int rt,int k){ int x=a[rt].f,y=a[x].f; a[x].son[k^1]=a[rt].son[k]; if(a[rt].son[k])a[a[rt].son[k]].f=x; a[rt].f=y; if(y)a[y].son[a[y].son[1]==x]=rt; a[x].f=rt; a[rt].son[k]=x; pushup(x);pushup(rt); } void splay(int rt,int ancestry){ while(a[rt].f!=ancestry){ int x=a[rt].f,y=a[x].f; if(y==ancestry)turn(rt,a[x].son[0]==rt); else{ int k=a[y].son[0]==x?1:0; if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);} else{turn(x,k);turn(rt,k);} } } if(ancestry==0)root=rt; } int newnode(int l,int r){ int rt=++size; a[rt].son[0]=a[rt].son[1]=a[rt].f=0; a[rt].l=l;a[rt].r=r; a[rt].s=r-l+1; return rt; } inline void buildtree(){ root=newnode(1,n); a[root].s=n; pos[n]=root; } int kth(int rt,int k){ if(k>a[rt].s)return 0; while(k){ int s=a[a[rt].son[0]].s+a[rt].r-a[rt].l+1; if(a[a[rt].son[0]].s<k&&k<=s){ k-=a[a[rt].son[0]].s; break; } if(s<k){ k-=s; rt=a[rt].son[1]; } else rt=a[rt].son[0]; } return a[rt].l+k-1; } void remove(int rt){ int front=a[rt].son[0],next=a[rt].son[1]; while(a[front].son[1])front=a[front].son[1]; while(a[next].son[0])next=a[next].son[0]; if(!front&&!next)root=0; else if(!front){ splay(next,root); root=next; a[root].f=0; a[rt].son[0]=a[rt].son[1]=0; a[rt].s=1; } else if(!next){ splay(front,root); root=front; a[root].f=0; a[rt].son[0]=a[rt].son[1]=0; a[rt].s=1; } else{ splay(front,0);splay(next,front); a[next].son[0]=a[rt].f=0; a[rt].s=1; pushup(next);pushup(front); } } void split(int x,int id){ if(a[x].l==a[x].r)return; int l=a[x].l,r=a[x].r,lson,rson; if(l==id){ rson=newnode(l+1,r); pos[r]=rson;pos[id]=x; a[rson].son[1]=a[x].son[1]; a[a[rson].son[1]].f=rson; a[x].son[1]=rson;a[rson].f=x; a[x].r=l; pushup(rson);pushup(x); } else if(r==id){ lson=newnode(l,r-1); pos[r-1]=lson;pos[id]=x; a[lson].son[0]=a[x].son[0]; a[a[lson].son[0]].f=lson; a[x].son[0]=lson;a[lson].f=x; a[x].l=r; pushup(lson);pushup(x); } else{ lson=newnode(l,id-1);rson=newnode(id+1,r); pos[id]=x;pos[id-1]=lson;pos[r]=rson; a[lson].son[0]=a[x].son[0];a[rson].son[1]=a[x].son[1]; a[a[lson].son[0]].f=lson;a[a[rson].son[1]].f=rson; a[x].son[0]=lson;a[x].son[1]=rson;a[lson].f=a[rson].f=x; a[x].l=a[x].r=id; pushup(lson);pushup(rson);pushup(x); } splay(x,0); } inline int change(int x,int y){ int k=pos.lower_bound(x)->second,s; split(k,x); splay(k,0); s=a[k].s-a[a[k].son[1]].s; a[k].l=a[k].r=y; pos[y]=k; return s; } inline void push_head(int rt){ if(!root){root=rt;return;} int fa=root; while(a[fa].son[0]){ a[fa].s++; fa=a[fa].son[0]; } a[fa].s++; a[fa].son[0]=rt; a[rt].f=fa; splay(rt,0); } inline void push_last(int rt){ if(!root){root=rt;return;} int fa=root; while(a[fa].son[1]){ a[fa].s++; fa=a[fa].son[1]; } a[fa].s++; a[fa].son[1]=rt; a[rt].f=fa; splay(rt,0); } inline int make_head(int x){ int k=pos.lower_bound(x)->second,s; split(k,x); splay(k,0); s=a[k].s-a[a[k].son[1]].s; remove(k); push_head(k); return s; } inline int make_last(int x){ int k=pos.lower_bound(x)->second,s; split(k,x); splay(k,0); s=a[k].s-a[a[k].son[1]].s; remove(k); push_last(k); return s; } void work(){ int f,x,y,last=0; while(m--){ f=read();x=read()-last; switch(f){ case 1:{ y=read()-last; last=change(x,y); printf("%d\n",last); break; } case 2:{ last=make_head(x); printf("%d\n",last); break; } case 3:{ last=make_last(x); printf("%d\n",last); break; } case 4:{ last=kth(root,x); printf("%d\n",last); break; } } } } void init(){ n=read();m=read(); buildtree(); } int main(){ init(); work(); return 0; }