Luogu

BZOJ

分析

手玩一下这个旋转的过程,发现最大/最小值旋到根,就是把它的儿子给父亲,接着原来的根变成它的儿子,然后它变成根。

于是用$\mathrm{LCT}$来维护一下$\mathrm{spaly}$上的父子关系,这样就可以解决后面四个操作。

考虑第一个操作怎么做。显然一个点要么放在前驱的右儿子上,要么放在后继的左儿子上。

于是用一个$\mathrm{set}$来求前驱和后继。可以发现前驱的右儿子和后继的左儿子一定有一个为空,直接接上去就行了。

注意要特判已经为根的情况。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int m,root,tot=0;
int fa[N],lson[N],rson[N];

struct Link_Cut_Tree {
    int fa[N],ch[N][2],sz[N],sta[N],rev[N];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }
    inline void reverse(int x) { swap(ch[x][0],ch[x][1]); rev[x]^=1; }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y))
                rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x])
            splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x); splay(x); reverse(x); }
    inline void split(int x,int y) { makeroot(x); access(y); splay(y); }
    inline void link(int x,int y) { makeroot(x); fa[x]=y; }
    inline void cut(int x,int y) { split(x,y); fa[x]=ch[y][0]=0; pushup(y); }
    inline int query(int x) { split(x,root); return sz[root]; } //查询深度
} T;

map<int,int> mp;
set<int> S;

inline void insert(int x) {
    int u=mp[x]=++tot;
    if (S.empty()) { S.insert(x),root=u; puts("1"); return; }
    set<int>::iterator it=S.upper_bound(x);
    if (it==S.end()||lson[mp[*it]]) {
        --it; int v=mp[*it];
        T.link(u,v),fa[u]=v,rson[v]=u;
    } else {
        int v=mp[*it];
        T.link(u,v),fa[u]=v,lson[v]=u;
    }
    S.insert(x); printf("%d\n",T.query(u));
}

inline void spaly_min() {
    int u=mp[*S.begin()];
    if (root==u) { puts("1"); return; }
    printf("%d\n",T.query(u));
    T.cut(u,fa[u]); if (rson[u]) T.cut(u,rson[u]);
    T.link(u,root); if (rson[u]) T.link(fa[u],rson[u]);
    lson[fa[u]]=rson[u]; if (rson[u]) fa[rson[u]]=fa[u];
    fa[u]=0,fa[root]=u,rson[u]=root,root=u;
}

inline void spaly_max() {
    int u=mp[*S.rbegin()];
    if (root==u) { puts("1"); return; }
    printf("%d\n",T.query(u));
    T.cut(u,fa[u]); if (lson[u]) T.cut(u,lson[u]);
    T.link(u,root); if (lson[u]) T.link(fa[u],lson[u]);
    rson[fa[u]]=lson[u]; if (lson[u]) fa[lson[u]]=fa[u];
    fa[u]=0,fa[root]=u,lson[u]=root,root=u;
}

inline void spaly_del_min() {
    int u=mp[*S.begin()];
    if (root==u) {
        puts("1"); S.erase(S.begin());
        if (rson[u]) T.cut(u,rson[u]);
        fa[rson[u]]=0,root=rson[u];
        return;
    }
    printf("%d\n",T.query(u)); S.erase(S.begin());
    T.cut(u,fa[u]); if (rson[u]) T.cut(u,rson[u]),T.link(fa[u],rson[u]);
    lson[fa[u]]=rson[u]; if (rson[u]) fa[rson[u]]=fa[u];
}

inline void spaly_del_max() {
    int u=mp[*S.rbegin()];
    if (root==u) {
        puts("1"); S.erase(--S.end());
        if (lson[u]) T.cut(u,lson[u]);
        fa[lson[u]]=0,root=lson[u];
        return;
    }
    printf("%d\n",T.query(u)); S.erase(--S.end());
    T.cut(u,fa[u]); if (lson[u]) T.cut(u,lson[u]),T.link(fa[u],lson[u]);
    rson[fa[u]]=lson[u]; if (lson[u]) fa[lson[u]]=fa[u];
}

int main() {
    m=read();
    while (m--) {
        int op=read();
        if (op==1) insert(read());
        else if (op==2) spaly_min();
        else if (op==3) spaly_max();
        else if (op==4) spaly_del_min();
        else spaly_del_max();
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 17 PM