維護集合Ⅱ【Splay】

題目描述

如未特别說明，以下所有資料均為整數。

維護一個多重集 S ，初始為空，有以下幾種操作：

1. 插入元素 x 。
2. 删除元素 x ，保證删除的元素一定存在。

3. 輸出 S 中相差最小的兩個元素的差，保證此時|S|≥2 。

   操作共 n 次 。

輸入格式

第一行一個整數 n (1≤n≤3×10^5)，表示共有 n 次操作。

接下來 n 行，每行為以下幾種格式之一：

0 x ，把 x（0≤x≤10^9 ）加入 S 。

1 x ，删除 x 。

2 ，回答詢問：S 中相差最小的兩個元素的差是多少？

輸出格式

對于每次詢問，輸出單獨一行表示答案。

樣例資料 1

輸入

5

0 3

0 7

2

0 4

2

輸出

4

1

解題思路：

用Splay維護每個數與它的前驅（小于等于它的最大數）的差及子樹中差的最小值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

int getint()
{
    int i=,f=;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<)+(i<<)+c-'0';
    return i*f;
}

const int N=,INF=;
int tot,root,val[N],d[N],mi[N],fa[N],son[N][];

int which(int x)
{
    return son[fa[x]][]==x;
}

void Rotate(int x)
{
    int y=fa[x],z=fa[y],t=which(x);
    if(y!=root)son[z][which(y)]=x;
    else root=x;
    fa[x]=z,fa[y]=x;
    son[y][t]=son[x][t^],son[x][t^]=y;
    if(son[y][t])fa[son[y][t]]=y;
    mi[x]=mi[y];
    mi[y]=min(d[y],min(mi[son[y][]],mi[son[y][]]));
}

void Splay(int x,int f)
{
    while(fa[x]!=f)
    {
        if(fa[fa[x]]!=f)
            which(x)==which(fa[x])?Rotate(fa[x]):Rotate(x);
        Rotate(x);
    }
}

void Insert(int &u,int v,int f)
{
    if(!u)
    {
        u=++tot,val[u]=v,fa[u]=f;
        return;
    }
    if(v<=val[u])Insert(son[u][],v,u);
    else Insert(son[u][],v,u);
}

int getpre(int x)
{
    x=son[x][];
    while(son[x][])x=son[x][];
    return x;
}

int getsuf(int x)
{
    x=son[x][];
    while(son[x][])x=son[x][];
    return x;
}

void modify(int x)
{
    int y;
    Splay(x,);
    if(son[x][])
    {
        y=getpre(x);
        d[x]=val[x]-val[y];
        mi[x]=min(d[x],mi[x]);
    }
    if(son[x][])
    {
        y=getsuf(x);
        Splay(y,x);
        d[y]=val[y]-val[x];
        mi[y]=min(d[y],min(mi[son[y][]],mi[son[y][]]));
        mi[x]=min(mi[y],mi[x]);
    }
}

int find(int u,int v)
{
    if(val[u]==v)return u;
    if(v<val[u])return find(son[u][],v);
    return find(son[u][],v);
}

void Delete(int v)
{
    int x=find(root,v);
    Splay(x,);
    if(!son[x][]&&!son[x][])
    {
        root=;
        return;
    }
    if(!son[x][])
    {
        int y=getsuf(x);
        Splay(y,x);
        root=y,fa[y]=;
        d[y]=INF,mi[y]=mi[son[y][]];
        return;
    }
    if(!son[x][])
    {
        root=son[x][],fa[root]=;
        return;
    }
    int y=getsuf(x),z=getpre(x);
    Splay(y,x),Splay(z,x);
    d[y]=val[y]-val[z];
    mi[y]=min(d[y],min(mi[z],mi[son[y][]]));
    root=y,fa[y]=,son[y][]=z;
    fa[z]=y;
}

int main()
{
    //freopen("lx.in","r",stdin);
    //freopen("lx.out","w",stdout);
    memset(mi,INF,sizeof(mi));
    memset(d,INF,sizeof(d));
    int n,op,x;
    n=getint();
    while(n--)
    {
        op=getint();
        if(op==)
        {
            x=getint();
            Insert(root,x,);
            modify(tot);
        }
        else if(op==)
        {
            x=getint();
            Delete(x);
        }
        else cout<<mi[root]<<'\n';
    }
    return ;
}