方伯伯的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% 的数据，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+>=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 ;

}

巴特西

方伯伯的OJ ( onlinejudge )