题意

初始有 \(n\) 个人，编号为 \(1\sim n\)，每个人有一个排名，初始排名即编号。现在有 \(m\) 次操作：

• 将编号为 \(x\) 的人编号改为 \(y\)，排名不变。保证当前没有编号为 \(y\) 的人。
• 将编号为 \(x\) 的人的排名改为 \(1\)
• 将编号为 \(x\) 的人的排名改为 \(n\)
• 查询排名为 \(k\) 的用户的编号

强制在线。

\(1 \leq n \leq 10^8,1 \leq m \leq 10^5,1 \leq y \leq 2 \times 10^8 ,1 \leq k \leq n\)

题解

平衡树。观察到 \(n\) 很大，\(m\) 却只有 \(10^5\)，说明有些点不会用到。我们把一段没有用到的区间存成一个点。每次需要用到编号 \(x\) 的时候，就把 \(x\) 从当前区间 \([l,r]\) 里取出来，变成 \([l,x-1],[x,x],[x+1,r]\) 三个点（当然，当 \(x=l\) 或 \(x=r\) 时有一些点不会存在）。剩下的部分就是区间平衡树的操作。

代码实现略微复杂，提供了部分注释。

# include <bits/stdc++.h>

const int N=500010,INF=0x3f3f3f3f;

struct Node{
	int l,r;
	int lc,rc;
	int rnd,fa,size;
}tree[N];
int cnt,root;
std::map <int,int> idx;

int n,m;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void NewNode(int &x,int l,int r){
	x=++cnt;
	tree[x].l=l,tree[x].r=r,tree[x].rnd=rand(),tree[x].size=r-l+1;
	idx[l]=x; // idx[a] 的含义是 大于等于 a 的数在树上的节点编号为 idx[a]
	return;
}
inline int& lc(int x){
	return tree[x].lc;
}
inline int& rc(int x){
	return tree[x].rc;
}
inline int& fa(int x){
	return tree[x].fa;
}
inline void update(int x){
	tree[x].size=tree[lc(x)].size+tree[rc(x)].size+tree[x].r-tree[x].l+1;
	if(lc(x)) // 避免 fa(0) 乱指出现问题
		fa(lc(x))=x; 
	if(rc(x))
		fa(rc(x))=x;
	return;
}
void merge(int &now,int x,int y){
	if(!x||!y){
		now=x|y;
		return;
	}
	if(tree[x].rnd<tree[y].rnd){
		now=x;
		merge(rc(now),rc(x),y);
		update(now);
	}else{
		now=y;
		merge(lc(now),x,lc(y));
		update(now);
	}
	return;
}
void split(int now,int k,int &x,int &y){ // 将平衡树前 k 个位置分裂
    // 需要注意 调用的时候必须保证前 k 个位置恰好可以分裂出来（即不能存在一个节点 [l,r] 满足 l<=k 但 r>k
    // 通俗地讲就是一个节点不能被砍成两半
	if(!now){
		x=y=0;
		return;
	}
	if(k<=tree[lc(now)].size){
		y=now;
		split(lc(now),k,x,lc(y));
		update(y);
	}else{
		x=now;
		split(rc(now),k-tree[lc(now)].size-(tree[now].r-tree[now].l+1),rc(x),y);
		update(x);
	}
	return;
}
inline void Insert(int x,int l,int r){ // 在位置 x 插入区间 [l,r]
	int a,b,seg;
	split(root,x-1,a,b),NewNode(seg,l,r),merge(a,a,seg),merge(root,a,b);
	return;
}
inline void Delete(int l,int r){ // 删除 **排名** 为 [l,r] 的位置
	int a,b,c;
	split(root,l-1,a,b);
	split(b,r-l+1,b,c);
	merge(root,a,c);
	return;
}
inline int presum(int x){ // 查询有多少个位置排名比 x 小
	int ans=tree[lc(x)].size;
    // 一路往上跳，如果自己是右儿子就加上左儿子的大小和父亲的大小
	while(fa(x)){
		if(rc(fa(x))==x)
			ans+=tree[lc(fa(x))].size+tree[fa(x)].r-tree[fa(x)].l+1;
		x=fa(x); 
	}
	return ans;
}
inline int Kth(int k,int x){ // 查排名为 k 的位置
	assert(tree[x].size>=k);
	while(1){
		if(k<=tree[lc(x)].size){
			x=lc(x);
			continue;
		}
		else if(k<=tree[lc(x)].size+tree[x].r-tree[x].l+1){ // 答案在这个区间中
			return tree[x].l+(k-tree[lc(x)].size-1);
		}
		k-=tree[lc(x)].size+tree[x].r-tree[x].l+1;
		x=rc(x);
	}
	return 114514;
}
int main(void){
	n=read(),m=read();
	Insert(1,1,n);
	int las=0,opt,x,y;
	while(m--){
		opt=read(),x=read()-las;
		switch(opt){
			case 1:{
				y=read()-las;
				std::map <int,int>:: iterator it=idx.lower_bound(x+1);
				--it; // 找到 x 在树上的节点编号 
				int opL=(*it).first,opR=tree[idx[opL]].r,treerk=presum(idx[opL]); // 查询所属区间和排名
				las=treerk+x-opL+1;
				printf("%d\n",las);
				Delete(treerk+1,treerk+1+opR-opL);
				if(x!=opL) // 把区间拆成 [l,x-1] [y,y] [x+1,r] 三部分
					Insert(treerk+1,opL,x-1);
				Insert(las,y,y);
				if(x!=opR)
					Insert(las+1,x+1,opR);
				break;
			}
			case 2:{
				std::map <int,int>::iterator it=idx.lower_bound(x+1);
				--it;
				int opL=(*it).first,opR=tree[idx[opL]].r,treerk=presum(idx[opL]);
				las=treerk+x-opL+1;
				printf("%d\n",las);
				Delete(treerk+1,treerk+1+opR-opL);
				if(x!=opL)
					Insert(treerk+1,opL,x-1);
				if(x!=opR)
					Insert(las,x+1,opR);
				Insert(1,x,x);
				break;
			}
			case 3:{
				std::map <int,int>::iterator it=idx.lower_bound(x+1);
				--it;
				int opL=(*it).first,opR=tree[idx[opL]].r,treerk=presum(idx[opL]);
				las=treerk+x-opL+1;
				printf("%d\n",las);
				Delete(treerk+1,treerk+1+opR-opL);
				if(x!=opL)
					Insert(treerk+1,opL,x-1);
				if(x!=opR)
					Insert(las,x+1,opR);
				Insert(n,x,x);
				break;
			}
			case 4:{
				printf("%d\n",las=Kth(x,root));
				break;
			}
		}
	}
	return 0;
}