BZOJ2028：[SHOI2009]会场预约（平衡树版）

浅谈\(splay\)：https://www.cnblogs.com/AKMer/p/9979592.html

浅谈\(fhq\)_\(treap\)：https://www.cnblogs.com/AKMer/p/9981274.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=2028

此题的线段树写法：https://www.cnblogs.com/AKMer/p/9948789.html

我如果要插入一个新的区间\([l,r]\)，会被这个预约冲掉的区间显然满足\(st\leqslant r\)且\(ed\geqslant l\)。对于这样的预约是连续的一段，于是我们就可以通过区间删除来达到踢出预约的效果了。那么怎么找这连续的一段区间呢？

对于\(splay\)

将结束时间严格小于\(l\)的预约旋到根，将起始时间严格大于\(r\)的预约旋到根的右儿子。那么根的右儿子的左子树里所有的预约就都是会被当前预约冲掉的预约，直接全部删掉就行了。

对于\(fhq\)_\(treap\)

将整个树分成三部分，第一部分满足所有结点结束时间严格小于\(l\)，第三部分满足所有结点起始时间严格大于\(l\)，然后直接把第二部分换成代表新的预约的结点\(merge\)起来就行了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

\(splay\)版代码如下：

#include <cstdio>

using namespace std;

const int maxn=2e5+5,inf=2e9;

int n;

char s[5];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct Splay {

    int tot,root;

    int fa[maxn],son[maxn][2];

    int val[maxn][2],siz[maxn];

    int newnode(int l,int r) {

        siz[++tot]=1;

        val[tot][0]=l,val[tot][1]=r;

        return tot;

    }

    int t(int u) {

        return son[fa[u]][1]==u;

    }

    void update(int u) {

        siz[u]=siz[son[u][0]]+1+siz[son[u][1]];

    }

    void rotate(int u) {

        int ret=t(u),f=fa[u],s=son[u][ret^1];

        son[f][ret]=s;if(s)fa[s]=f;son[u][ret^1]=f;

        fa[u]=fa[f];if(fa[f])son[fa[f]][t(f)]=u;

        fa[f]=u;update(f);update(u);

    }

    void splay(int goal,int u) {

        int tmp=fa[goal];

        while(fa[u]!=tmp) {

            if(fa[fa[u]]!=tmp) {

                if(t(fa[u])==t(u))rotate(fa[u]);

                else rotate(u);

            }

            rotate(u);

        }

        if(!tmp)root=u;

    }

    int find(int opt,int v) {

        int u=root;

        while(val[u][opt]!=v) {

            if(val[u][opt]<v) {if(son[u][1])u=son[u][1];else break;}

            if(val[u][opt]>v) {if(son[u][0])u=son[u][0];else break;}

        }

        return u;

    }

    int get_pre(int v) {

        int u=find(1,v);splay(root,u);

        if(val[u][1]<v)return u;

        u=son[u][0];

        while(son[u][1])u=son[u][1];

        return u;

    }

    int get_suc(int v) {

        int u=find(0,v);splay(root,u);

        if(val[u][0]>v)return u;

        u=son[u][1];

        while(son[u][0])u=son[u][0];

        return u;

    }

    void ins(int l,int r) {

        int u=get_pre(l),v=get_suc(r);

        splay(root,u);splay(son[root][1],v);

        son[v][0]=newnode(l,r);fa[tot]=v;

        update(v);update(u);

    }

    void prepare() {

        int a=newnode(-inf,-inf),b=newnode(inf,inf);

        son[a][1]=b;fa[b]=a;update(a);root=a;

    }

}T;

int main() {

    T.prepare();

    n=read();

    for(int i=1;i<=n;i++) {

        scanf("%s",s+1);

        if(s[1]=='B')printf("%d\n",T.siz[T.root]-2);

        else {

            int l=read(),r=read();

            int tmp=T.siz[T.root];

            T.ins(l,r);

            printf("%d\n",tmp-(T.siz[T.root]-1));

        }

    }

    return 0;

}

\(fhq\)_\(treap\)版代码如下：

#include <ctime>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

const int maxn=2e5+5;

int n;

char s[5];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct fhq_treap {

    int tot,root;

    int fix[maxn],son[maxn][2];

    int siz[maxn],val[maxn][2];

    int newnode(int l,int r) {

        fix[++tot]=rand();

        val[tot][0]=l,val[tot][1]=r;

        siz[tot]=1;return tot;

    }

    void update(int u) {

        siz[u]=siz[son[u][0]]+1+siz[son[u][1]];

    }

    int find(int u,int opt,int v,int bo) {

        if(!u)return 0;

        int ans=0;

        if(val[u][opt]>v)ans=find(son[u][0],opt,v,bo);

        else if(val[u][opt]==v)return siz[son[u][0]]+bo;

        else ans=siz[son[u][0]]+1+find(son[u][1],opt,v,bo);

        return ans;

    }

    pii split(int u,int rk) {

        if(!rk)return make_pair(0,u);

        if(rk==siz[u])return make_pair(u,0);

        if(siz[son[u][0]]>=rk) {

            pii tmp=split(son[u][0],rk);

            son[u][0]=tmp.second,update(u);

            return make_pair(tmp.first,u);

        }

        else {

            pii tmp=split(son[u][1],rk-siz[son[u][0]]-1);

            son[u][1]=tmp.first,update(u);

            return make_pair(u,tmp.second);

        }

    }

    int merge(int a,int b) {

        if(!a||!b)return a+b;

        if(fix[a]>fix[b])return son[a][1]=merge(son[a][1],b),update(a),a;

        else return  son[b][0]=merge(a,son[b][0]),update(b),b;

    }

    int ins(int l,int r) {

        int rk1=find(root,0,r,1),rk2=find(root,1,l,0);

        pii tmp1=split(root,rk1),tmp2=split(tmp1.first,rk2);

        root=merge(merge(tmp2.first,newnode(l,r)),tmp1.second);

        return siz[tmp2.second];

    }

}T;

int main() {

    srand(time(0));n=read();

    for(int i=1;i<=n;i++) {

        scanf("%s",s+1);

        if(s[1]=='B')printf("%d\n",T.siz[T.root]);

        else {

            int l=read(),r=read();

            printf("%d\n",T.ins(l,r));

        }

    }

    return 0;

}