方伯伯的OJ

题目描述

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

OJ 上注册了个用户,编号为1  n,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

1. 操作格式为1 x y,意味着将编号为的用户编号改为y,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证必然出现在队列中, 同时是一个当前不在排名中的编号。

2. 操作格式为2 x,意味着将编号为的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为用户的排名。

3. 操作格式为3 x,意味着将编号为的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为用户的排名。

4. 操作格式为4 k,意味着查询当前排名为的用户编号,执行完该操作后需要输出当前操作用户的编号。

但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:

a y a

a

a

a

其中为上一次操作得到的输出,一开始= 0。

例如:

上一次操作得到的输出是5

这一次操作的输入为:1 13 15

因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10

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

输入格式

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

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

输出格式

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

样例

样例输入

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

数据范围与提示


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+>=x){x-=tr[ls].sz;break;}
else x-=tr[ls].sz+tr[k].r-tr[k].l+,k=tr[k].ch[];

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[],f;
}tr[];
set<int>s;
map<int,int>ls,dy,id;
void print_a(int k){
if(!k)return;
print_a(tr[k].ch[]);
for(int i=tr[k].l;i<=tr[k].r;i++)printf("%d ",i);
print_a(tr[k].ch[]);
}
bool get(int x){return tr[tr[x].f].ch[]==x;}
void wh(int x){
tr[x].sz=tr[tr[x].ch[]].sz+tr[tr[x].ch[]].sz+tr[x].r-tr[x].l+;
}
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^];tr[tr[x].ch[wx^]].f=y;
tr[x].ch[wx^]=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,);
ans=tr[tr[rt].ch[]].sz;
ans+=t-(*pos)+;
printf("%d\n",ans);
}
void insert_Front(int x){
int k=rt;
while(tr[k].ch[])k=tr[k].ch[];
int p=++cnt;
tr[p].l=tr[p].r=x;tr[p].sz=;
tr[k].ch[]=p;tr[p].f=k;
for(int i=p;i;i=tr[i].f)wh(i);
s.insert(x);id[x]=cnt;
splay(p,);
}
void insert_Bottom(int x){
int k=rt;
while(tr[k].ch[])k=tr[k].ch[];
int p=++cnt;
tr[p].l=tr[p].r=x;tr[p].sz=;
tr[k].ch[]=p;tr[p].f=k;
for(int i=p;i;i=tr[i].f)wh(i);
s.insert(x);id[x]=cnt;
splay(p,);
//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[],rs=tr[rt].ch[];
if(!ls)rt=rs,tr[rs].f=;
else if(!rs)rt=ls,tr[ls].f=;
else {
while(tr[ls].ch[])ls=tr[ls].ch[];
while(tr[rs].ch[])rs=tr[rs].ch[];
splay(ls,);splay(rs,ls);
//print_a(rt);puts("");puts("------");
tr[tr[rt].ch[]].ch[]=;
wh(tr[rt].ch[]);wh(rt);
//print_a(rt);puts("");puts("------");
}
}
else if(x==l){ tr[rt].l=x+,wh(rt);
s.insert(x+);id[x+]=rt;
}
else if(x==r){
tr[rt].r=x-,wh(rt);
}
else {
int k=++cnt;
tr[k].l=x+;tr[k].r=tr[rt].r;
tr[rt].r=x-;
int rs=tr[rt].ch[];
if(rs){tr[k].ch[]=rs;tr[rs].f=k;}
tr[rt].ch[]=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+);id[x+]=k; }
if(!opt)insert_Front(x);
else insert_Bottom(x);
}
void Kth(int x){
int k=rt;
while(){
//printf("k:%d l=%d r=%d\n",k,tr[k].l,tr[k].r);
int ls=tr[k].ch[];
//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+>=x){x-=tr[ls].sz;break;}
else x-=tr[ls].sz+tr[k].r-tr[k].l+,k=tr[k].ch[];
}
//cout<<tr[k].l<<' '<<x<<endl;
int f=tr[k].l+x-;
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=;cnt=;
tr[].l=,tr[].r=n,tr[].sz=n;
s.insert();id[]=;
ans=;
//print_a(rt);puts("");
for(int i=,op,x,y;i<=m;i++){
scanf("%d%d",&op,&x);x-=ans;
if(op==){
scanf("%d",&y);
y-=ans;
int t=ls[x];if(!t)t=x;
ls[y]=t;dy[t]=y;
ask(t);
}
if(op==){
int t=ls[x];if(!t)t=x;
ask(t);add(t,);
}
if(op==){
int t=ls[x];if(!t)t=x;
ask(t);add(t,);
}
if(op==){
Kth(x);
}
//cout<<"root "<<rt<<endl;
//print_a(rt);puts("");puts("------");
}
return ;
}
 
05-11 17:52