「SCOI2014」方伯伯的Oj - 动态开点线段树

题目大意

    方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
    Oj上注册了$n$个用户，编号为$1\sim n$，一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：

1. 操作格式为$1 \ x \ y$，意味着将编号为$x$的用户编号改为$y$，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证$x$必然出现在队列中，同时$y$是一个当前不在排名中的编号。
2. 操作格式为$2 \ x$，意味着将编号为$x$的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为$x$用户的排名。
3. 操作格式为$3 \ x$，意味着将编号为$x$的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为$x$用户的排名。
4. 操作格式为$4 \ k$，意味着查询当前排名为$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$
    现在你截获丁方伯伯的所有操作，希望你能给出结果。

---

题目分析

这道题做法很多，什么两个splay，两个treap，map+treap/splay都可以做。
然而我用的动态开点线段树。

和NOIP2017D2T3类似，将排名移动到第一位或最后一位用动态开点线段树维护。
线段树左右边界开大一点，每次移动排名时往前和往后移动当前区间边界。
统计下size就可以搞事情了。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int L=-2e8,R=2e8; //boundary limit

struct Tree {
	Tree *ls,*rs;
	int size,val;
	Tree(int l=0,int r=0) {size=r-l+1;}
} *root=new Tree(L,R);

struct Segment_Tree {
#define mid ((left+right)>>1)
	void newnode(Tree *&now,int left,int right) {if(!now)now=new Tree(left,right);}
	void insert(Tree *&now,int left,int right,int tar,int val) {
		newnode(now,left,right);
		if(left==right) {now->val=val;return;}
		newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
		if(tar<=now->ls->size)insert(now->ls,left,mid,tar,val);
		else insert(now->rs,mid+1,right,tar-now->ls->size,val);
	}
	void remove(Tree *&now,int left,int right,int tar) {
		if(!now)now=new Tree(left,right);
		now->size--;
		if(left==right)return;
		newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
		if(tar<=now->ls->size)remove(now->ls,left,mid,tar);
		else remove(now->rs,mid+1,right,tar-now->ls->size);
	}
	int query(Tree *&now,int left,int right,int tar) {
		if(!now)now=new Tree(left,right);
		if(left==right)return now->val?now->val:left;
		newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
		if(tar<=now->ls->size)return query(now->ls,left,mid,tar);
		else return query(now->rs,mid+1,right,tar-now->ls->size);
	}
	int sum(Tree *&now,int left,int right,int Left,int Right) {
		if(Right<left||Left>right)return 0;
		if(!now)now=new Tree(left,right);
		if(Left<=left&&Right>=right)return now->size;
		return sum(now->ls,left,mid,Left,Right)+sum(now->rs,mid+1,right,Left,Right);
	}
} st;

map<int,int> id;
int n,m,ans=0;

int main() {
	n=Get_Int();
	m=Get_Int();
	int left=1,right=n;
	for(int i=1; i<=m; i++) {
		int opt=Get_Int();
		if(opt==1) {
			int x=Get_Int()-ans,y=Get_Int()-ans;
			id[y]=id.count(x)?id[x]:x;
			st.insert(root,L,R,st.sum(root,L,R,L,id[y]),y); //insert at id[y]
			printf("%d\n",ans=st.sum(root,L,R,left,id[y]));
		} else if(opt==2) {
			int x=Get_Int()-ans;
			ans=st.sum(root,L,R,left,id.count(x)?id[x]:x);
			printf("%d\n",ans);
			st.remove(root,L,R,left-L+ans);
			st.insert(root,L,R,left-L,x);
			id[x]=--left;
		} else if(opt==3) {
			int x=Get_Int()-ans;
			ans=st.sum(root,L,R,left,id.count(x)?id[x]:x);
			printf("%d\n",ans);
			st.remove(root,L,R,left-L+ans);
			st.insert(root,L,R,st.sum(root,L,R,L,right)+1,x);
			id[x]=++right;
		} else {
			int k=Get_Int()-ans;
			printf("%d\n",ans=st.query(root,L,R,left-L+k));
		}
	}
	return 0;
}