[Scoi2014]方伯伯的OJ（动态开点splay）

开始没看数据范围差点以为是这题了：https://www.cnblogs.com/hfctf0210/p/10911340.html

然后看到n<=1e8，怎么这么大？

所以这题需要用动态开点线段树或者动态开点splay，而我上面的那题写的树状数组，为了熟悉splay就用动态开点splay吧而且也不知道这题动态开点线段树怎么写。正常要开两棵splay，但是关于用户的一棵操作简单没有必要开，所以可以用map代替，为了方便lower_bound查询，map记录右端点。然后先要执行三个基本操作：1、查询第k大。2、查询k节点的rank。3、分裂节点，分裂就是直接开新节点即可。然后重点在于2,3操作，一种简便的方法就是将目标节点拆开并旋转到根，将左右子树合并，使其成为第一/倒一。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

struct node{int ch[],sz,l,r,fa;}t[N<<];

int n,m,root,cnt,ans;

map<int,int>mp;

int newnode(int l,int r)

{

    int k=++cnt;

    t[k].ch[]=t[k].ch[]=;

    t[k].l=l,t[k].r=r;

    t[k].sz=t[k].r-t[k].l+;

    return k;

}

void pushup(int k){t[k].sz=t[t[k].ch[]].sz+t[t[k].ch[]].sz+t[k].r-t[k].l+;}

int dir(int k){return t[t[k].fa].ch[]==k;}

void rotate(int x)

{

    int y=t[x].fa,z=t[y].fa,d1=dir(x),d2=dir(y);

    t[y].ch[d1]=t[x].ch[d1^];

    t[t[x].ch[d1^]].fa=y;

    t[z].ch[d2]=x;

    t[x].fa=z;

    t[y].fa=x;

    t[x].ch[d1^]=y;

    pushup(y),pushup(x);

}

void splay(int x,int goal)

{

    while(t[x].fa!=goal)

    {

        int y=t[x].fa,z=t[y].fa,d1=dir(x),d2=dir(y);

        if(z!=goal){if(d1==d2)rotate(y);else rotate(x);}

        rotate(x);

    }

    if(!goal)root=x;

}

int getkth(int rk)

{

    int k=root;

    while()

    {

        int son=t[k].ch[];

        if(rk<=t[t[k].ch[]].sz)k=t[k].ch[];

        else if(rk>t[t[k].ch[]].sz+t[k].r-t[k].l+)

        rk-=t[t[k].ch[]].sz+t[k].r-t[k].l+,k=t[k].ch[];

        else return t[k].l+rk-t[t[k].ch[]].sz-;

    }

}

int getrk(int k){splay(k,);return t[t[k].ch[]].sz+;}

void split(int k,int id)

{

    if(t[k].l==t[k].r)return;

    int l=,r=;

    mp[id]=k;

    if(t[k].l!=id)

    {

        mp[id-]=l=newnode(t[k].l,id-);

        t[l].ch[]=t[k].ch[];

        t[t[l].ch[]].fa=l;

        t[k].ch[]=l;

        t[l].fa=k;

    }

    if(t[k].r!=id)

    {

        mp[t[k].r]=r=newnode(id+,t[k].r);

        t[r].ch[]=t[k].ch[];

        t[t[r].ch[]].fa=r;

        t[k].ch[]=r;

        t[r].fa=k;

    }

    t[k].l=t[k].r=id;

    if(l)pushup(l);

    if(r)pushup(r);

    pushup(k);

}

void change(int k,int tp)

{

    splay(k,);

    k=root;

    if(!t[k].ch[tp])return;

    if(!t[k].ch[tp^])t[k].ch[tp^]=t[k].ch[tp],t[k].ch[tp]=;

    else{

        k=t[k].ch[tp^];

        while(t[k].ch[tp])k=t[k].ch[tp];

        t[t[root].ch[tp]].fa=k;

        t[k].ch[tp]=t[root].ch[tp];

        t[root].ch[tp]=;

        splay(t[k].ch[tp],);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    root=mp[n]=newnode(,n);

    while(m--)

    {

        int op,x,y,pos;scanf("%d%d",&op,&x),x-=ans;

        if(op==)

        {

            scanf("%d",&y),y-=ans;

            pos=(*mp.lower_bound(x)).second;

            split(pos,x);

            printf("%d\n",ans=getrk(pos));

            t[pos].l=t[pos].r=y;

            mp[y]=pos;

        }

        else if(op==)printf("%d\n",ans=getkth(x));

        else{

            int pos=(*mp.lower_bound(x)).second;

            split(pos,x);

            printf("%d\n",ans=getrk(pos));

            change(pos,op-);

        }

    }

}

巴特西

[Scoi2014]方伯伯的OJ（动态开点splay）

最新文章

热门文章