题目要求维护一个编号序列和一个排名序列，并支持四种操作：
1.按照编号修改编号，并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名，然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8，那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续：这一题是我在190103的时候写完的，然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用，这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误，进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后，经由此处，我发现有个节点的相邻节点是一个大小为空的节点，进而发现这个节点在被分配下标之前就被访问了。
最终，我注意到它第一次出现所相接的节点，并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错，并通过了此题。
注意点：
1.对于空节点的情况一定要认真考虑，因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」！！！！！！
4.如果一个点本来就是排名最后的点而要移到排名最后，有可能会出错。
#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);
bool bo=0;
class Splay{
public:
class Node{
public:
int l;
int r;
int sz;
int sn[2];
int fa;
inline void set(int L,int R,int FA){
l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
}
};
//i表示mp[i]这个节点的右端点的标号。
std::map<int,int> mp;
Node tr[400005];
int cnt,rt;
//寻找当前节点与父亲的关系。
inline int fndD(int X){
return tr[tr[X].fa].sn[1]==X;
}
//更新当前节点。
inline void updt(int X){
tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
// if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
}
//旋转套装。
inline void splayOne(int X){
if(!X){return;}
int D=fndD(X),D2=fndD(tr[X].fa);
// if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
// puts("FKFKFK");
// printf("X");debug(X);
// printf("FA");debug(tr[X].fa);
// printf("BR");debug(tr[tr[X].fa].sn[D^1]);
// }
tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
updt(tr[X].sn[D^1]),updt(X);
}
inline void splayTwo(int X){
// if(bo&&X==38190){debug(X);}
int D=fndD(X),D2=fndD(tr[X].fa);
tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
}
inline void splayRnw(int X){
while(tr[X].fa){splayTwo(X);}
rt=X;
}
// inline void splayRnw(int X){
// while(tr[X].fa){
// int F=tr[X].fa,FF=tr[tr[X].fa].fa;
// if(!FF)
// }
// }
//找到排名为X的元素。
inline int fnd(int X){
int P=rt;
while(P){
if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
P=tr[P].sn[1];
}else if(X>tr[tr[P].sn[0]].sz){
X-=tr[tr[P].sn[0]].sz;
splayRnw(P);
// debug(P);
return tr[P].l+X-1;
}else{
P=tr[P].sn[0];
}
}
return -1;
}
//开一个新节点，以X为它的父亲。
inline int nwlc(int X,int L,int R){
int P=++cnt;
// if(P==65505){
// printf("START:");
// debug(P);
// }
tr[P].set(L,R,X);
return P;
}
//将编号为X的节点单独弄成一个新的节点，然后将它的两个子节点接到它的左右，并更改相应的编号的映射
inline int split(int P,int X){
if(tr[P].l==tr[P].r){return P;}
if(P==-1){return error(192600404),192600404;}
if(X>tr[P].l){
int L=tr[P].sn[0];
L?(cut(L),0):(tr[0].fa=0);
tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
L?(cnnct(L,tr[P].sn[0],0),0):0;
mp[X-1]=tr[P].sn[0];
// updt(tr[P].sn[0]);
}
if(X<tr[P].r){
int R=tr[P].sn[1];
R?(cut(R),1):(tr[0].fa=0);
tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
R?(cnnct(R,tr[P].sn[1],1),1):1;
mp[tr[P].r]=tr[P].sn[1];
// updt(tr[P].sn[1]);
}
tr[P].l=tr[P].r=X;mp[X]=P;
updt(P);
return P;
}
inline int fndMn(int X){
int P=X,FP=tr[X].fa;
while(P){
FP=P;
P=tr[P].sn[0];
}
return FP;
}
inline int fndMx(int X){
int P=X,FP=tr[X].fa;
while(P){
FP=P;
P=tr[P].sn[1];
}
return FP;
}
inline void cut(int X){
int D=fndD(X);
tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
}
inline void cnnct(int X,int Y,int D){
tr[Y].sn[D]=X,tr[X].fa=Y;
updt(Y);
}
inline void prnt(int X,int dep=0){
if(!X){return;}
for(int i=1;i<=dep;++i){
printf(" ");
}debug(X);
prnt(tr[X].sn[0],dep+1);
prnt(tr[X].sn[1],dep+1);
}
public:
inline int CHANGE(int X,int Y){
int P=mp.lower_bound(X)->second;
P=split(P,X);
tr[P].l=tr[P].r=Y;
mp[Y]=P;
splayRnw(P);
return tr[tr[P].sn[0]].sz+1;
}
inline int LST(int X){
int P=mp.lower_bound(X)->second;
P=split(P,X);
splayRnw(P);
int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
if(!L){
return RT;
}
R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。
return RT;
}
inline int RST(int X){
int P=mp.lower_bound(X)->second;
P=split(P,X);
splayRnw(P);
int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
if(!R){
return RT;
}
L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
return RT;
}
inline int ARNK(int X){
return fnd(X);
}
//初始化。
inline void INIT(int N){
cnt=1;
rt=1;
tr[1].set(1,N,0);
mp[N]=1;
}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。
*/
int n,m;
Splay T;
void init(){
int code=0;
scanf("%d%d",&n,&m);
T.INIT(n);
int op,x,y;
for(int i=1;i<=m;++i){
scanf("%d",&op);
switch(op){
case 1:{
scanf("%d%d",&x,&y);
x-=code,y-=code;
printf("%d\n",code=T.CHANGE(x,y));
// if(code==95204&&i>=80000){
// puts("fk1");
// printf("%d\n",x);
// return;
// }
break;
}
case 2:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.LST(x));
break;
}
case 3:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.RST(x));
break;
}
case 4:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.ARNK(x));
break;
}
}
// printf("CORESIZE:%d\n",T.tr[54567].sz);
}
}
int main(){
// freopen("input1.in","r",stdin);
// freopen("output1.out","w",stdout);
init();
return 0;
}