方伯伯的OJ ( onlinejudge )

方伯伯的OJ

题目描述

方伯伯正在做他的OJ。现在他在处理OJ 上的用户排名问题。

OJ 上注册了n 个用户，编号为1 ∼ 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

现在你截获了方伯伯的所有操作，希望你能给出结果。

 

输入格式

输入的第1 行包含2 个用空格分隔的整数n 和m，表示初始用户数和操作数。

此后有m 行，每行是一个询问，询问格式如上所示。

 

输出格式

输出包含m 行。每行包含一个整数，其中第i 行的整数表示第i 个操作的输出。

 

样例

样例输入

10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

样例输出

2
2
2
4
3
5
5
7
8
11

数据范围与提示

 

【数据范围】

对于10% 的数据，1 ≤ n ≤ 10^3

 

对于40% 的数据，1 ≤ n ≤ 10^5

 

对于100% 的数据，1 ≤ n ≤ 10^8，1 ≤ m ≤ 105

 

输入保证对于所有的操作1，2，3，x 必然已经出现在队列中，同时对于所有操作1，1 ≤ y ≤ 2 ×10^8，并且 y 没有出现在队列中。 对于所有操作4，保证1 ≤ k ≤ n。

---

solution

可以发现1e8的数据啥也开不起来。

我们考虑用 splay 维护一段区间，这样的状态数是m了。

还是以splay的大小关系表示排名，节点维护区间长度。

对于1操作，我们用两个map将编号对应到 1~1e8

对于2.3操作，我们找到包含这个点的区间。然后把它拆成三块。

对于4操作，splay上找k大即可。

现在还剩一个问题，怎么找到包含某个点的区间。

邵神犇：用一个set把当前所有区间的左端点存起来，每次找第一个包含它的。（%%%

那就解决啦。

然而这题全是细节。。。

1.找第k大时找到了也要减左儿子

if(tr[ls].sz>=x)k=ls;
else if(tr[ls].sz+tr[k].r-tr[k].l+1>=x){x-=tr[ls].sz;break;}
else x-=tr[ls].sz+tr[k].r-tr[k].l+1,k=tr[k].ch[1];

2.insert完要维护一整条链。

3.区间的size为r-l+1

4.根的前驱不是左儿子!!根的后驱不是右儿子!!(可能是我傻逼)

5.注意分讨x=l x=r x=l=r的特殊情况

6.节点开2m~3m

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
int n,m,rt,ans,cnt;
struct node{int sz,l,r,ch[2],f;
}tr[200006];
set<int>s;
map<int,int>ls,dy,id;
void print_a(int k){if(!k)return;print_a(tr[k].ch[0]);for(int i=tr[k].l;i<=tr[k].r;i++)printf("%d ",i);print_a(tr[k].ch[1]);
}
bool get(int x){return tr[tr[x].f].ch[1]==x;}
void wh(int x){tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].r-tr[x].l+1;
}
void rotate(int x){int y=tr[x].f,z=tr[y].f;int wx=get(x),wy=get(y);tr[z].ch[wy]=x;tr[x].f=z;tr[y].ch[wx]=tr[x].ch[wx^1];tr[tr[x].ch[wx^1]].f=y;tr[x].ch[wx^1]=y;tr[y].f=x;wh(y);wh(x);
}
void splay(int x,int g){while(tr[x].f!=g){int y=tr[x].f,z=tr[y].f;if(z!=g)rotate(get(x)==get(y)?y:x);rotate(x);}if(!g)rt=x;
}
void ask(int t){set<int>::iterator pos;pos=s.upper_bound(t);pos--;int k=id[*pos];//cout<<"aaa "<<t<<' '<<*pos<<' '<<k<<' '<<tr[k].l<<' '<<tr[k].r <<endl;splay(k,0);ans=tr[tr[rt].ch[0]].sz;ans+=t-(*pos)+1;printf("%d\n",ans);
}
void insert_Front(int x){int k=rt;while(tr[k].ch[0])k=tr[k].ch[0];int p=++cnt;tr[p].l=tr[p].r=x;tr[p].sz=1;tr[k].ch[0]=p;tr[p].f=k;for(int i=p;i;i=tr[i].f)wh(i);s.insert(x);id[x]=cnt;splay(p,0);
}
void insert_Bottom(int x){int k=rt;while(tr[k].ch[1])k=tr[k].ch[1];int p=++cnt;tr[p].l=tr[p].r=x;tr[p].sz=1;tr[k].ch[1]=p;tr[p].f=k;for(int i=p;i;i=tr[i].f)wh(i);s.insert(x);id[x]=cnt;splay(p,0);
//cout<<p<<' '<<tr[p].l<<' '<<tr[p].r<<' '<<tr[p].f<<endl; 
}
void add(int x,int opt){int l=tr[rt].l,r=tr[rt].r;if(l==r){int ls=tr[rt].ch[0],rs=tr[rt].ch[1];if(!ls)rt=rs,tr[rs].f=0;else if(!rs)rt=ls,tr[ls].f=0;else {while(tr[ls].ch[1])ls=tr[ls].ch[1];while(tr[rs].ch[0])rs=tr[rs].ch[0];splay(ls,0);splay(rs,ls);//print_a(rt);puts("");puts("------");tr[tr[rt].ch[1]].ch[0]=0;wh(tr[rt].ch[1]);wh(rt);//print_a(rt);puts("");puts("------");
        }}else if(x==l){tr[rt].l=x+1,wh(rt);s.insert(x+1);id[x+1]=rt;}else if(x==r){tr[rt].r=x-1,wh(rt);}else {int k=++cnt;tr[k].l=x+1;tr[k].r=tr[rt].r;tr[rt].r=x-1;int rs=tr[rt].ch[1];if(rs){tr[k].ch[1]=rs;tr[rs].f=k;}tr[rt].ch[1]=k;tr[k].f=rt;wh(k);wh(rt);//printf("id%d l=%d r=%d rs=%d k=%d\n",rt,tr[rt].l,tr[rt].r,tr[rt].ch[1],k);//printf("kid%d kl=%d lr=%d\n",k,tr[k].l,tr[k].r);s.insert(x+1);id[x+1]=k;}if(!opt)insert_Front(x);else insert_Bottom(x);
}
void Kth(int x){int k=rt;while(1){//printf("k:%d l=%d r=%d\n",k,tr[k].l,tr[k].r);int ls=tr[k].ch[0];//printf("sz:%d\n",tr[ls].sz);if(tr[ls].sz>=x)k=ls;else if(tr[ls].sz+tr[k].r-tr[k].l+1>=x){x-=tr[ls].sz;break;}else x-=tr[ls].sz+tr[k].r-tr[k].l+1,k=tr[k].ch[1];}//cout<<tr[k].l<<' '<<x<<endl;int f=tr[k].l+x-1;ans=dy[f];if(!ans)ans=f;printf("%d\n",ans);
}int main()
{freopen("test.in","r",stdin);freopen("test.out","w",stdout);cin>>n>>m;rt=1;cnt=1;tr[1].l=1,tr[1].r=n,tr[1].sz=n;s.insert(1);id[1]=1;ans=0;//print_a(rt);puts("");for(int i=1,op,x,y;i<=m;i++){scanf("%d%d",&op,&x);x-=ans;if(op==1){scanf("%d",&y);y-=ans;int t=ls[x];if(!t)t=x;ls[y]=t;dy[t]=y;ask(t);}if(op==2){int t=ls[x];if(!t)t=x;ask(t);add(t,0);}if(op==3){int t=ls[x];if(!t)t=x;ask(t);add(t,1);}if(op==4){Kth(x);}//cout<<"root "<<rt<<endl;//print_a(rt);puts("");puts("------");
    }return 0;
}