BZOJ3595: [Scoi2014]方伯伯的Oj

时间:2022-12-16 12:52:44

BZOJ3595: [Scoi2014]方伯伯的Oj

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

Sample Output

2
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;
}