冈字OI 1E14514 ms,氓新求助
查看原帖
冈字OI 1E14514 ms,氓新求助
538609
Neutralized楼主2022/2/8 10:50

删除的时候是用的把前驱和后继拉上来,然后孤立x点的方法
把前驱当作根,后继当作辅助点可以100pts AC\texttt{100pts \color{lightgreen}AC}(没有注释掉的erase
但是调换一下就44pts WA\texttt{44pts \color{red}WA}(注释掉的erase
私以为这两个应该是等价的啊……
Ball 聚捞解答

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define MAXN 200001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;

namespace SlowIO{
    Tp inline void rd(T &x){
        x=0; bool f=1; char in=g();
        while(!isdigit(in)) f&=(in!='-'),in=g();
        while(isdigit(in)) x=(x<<3)+(x<<1)+(in^48),in=g();
        x*=((f<<1)-1);
    }
    Tp inline void op(T x){
        if(x<0) pc('-'),x=-x;
        if(x>=10) op(x/10);
        pc(x%10+48);
    }
    Tp inline void writeln(T x){ op(x),pc('\n'); }
    Tp inline void writesp(T x){ op(x),pc(' '); }
    Tp inline void writespf(T x){ pc(' '),op(x); }
}; using namespace SlowIO;

namespace SplayTree{
    const int inf=2147483647;
    int root,tot,siz[MAXN];
    int fa[MAXN],son[MAXN][2];
    int val[MAXN],cnt[MAXN];

    inline void update(int x){ siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x]; }
    inline bool chk(int x){ return x==son[fa[x]][1]; }
    inline void rotate(int x){
        ri ff=fa[x],ac=fa[ff]; //father & ancestor
        register bool k=chk(x);
        son[ac][chk(ff)]=x; //置换x和ff
        fa[x]=ac;
        son[ff][k]=son[x][k^1]; //给ff换上新son
        fa[son[x][k^1]]=ff;
        son[x][k^1]=ff; //把ff变成son
        fa[ff]=x;
        update(ff),update(x); //上传
    } //旋转x
    inline void splay(int x,int tar){
        while(fa[x]!=tar){
            ri ff=fa[x],ac=fa[ff];
            if(ac!=tar) rotate(chk(ff)^chk(x)?x:ff);
            rotate(x);
        } if(!tar) root=x;
    } //伸展为tar的son
    inline void find(int x){
        ri cur=root;
        if(!cur) return;
        while(son[cur][val[cur]<x]&&val[cur]!=x)
        cur=son[cur][val[cur]<x];
        splay(cur,0);
    } //把最接近x的值旋转到根
    inline void insert(int x){
        ri cur=root,ff=0;
        while(cur&&val[cur]!=x)
        ff=cur,cur=son[cur][val[cur]<x];
        if(cur) ++cnt[cur];
        else{
            cur=++tot;
            if(ff) son[ff][val[ff]<x]=cur;
            val[cur]=x,fa[cur]=ff;
            siz[cur]=cnt[cur]=1;
        } splay(cur,0);
    } //插入x
    inline int fixes(int x,bool f){
        find(x); ri cur=root;
        if(val[cur]<x&&!f) return cur;
        if(val[cur]>x&&f) return cur;
        cur=son[cur][f],f^=1;
        while(son[cur][f]) cur=son[cur][f];
        return cur;
    } //找前后缀 0前缀 1后缀
    inline int getkth(int k){
        ri cur=root;
        while(cur){
            if(son[cur][0]&&k<=siz[son[cur][0]]) cur=son[cur][0];
            else{
                k-=siz[son[cur][0]]+cnt[cur];
                if(k<=0){
                    splay(cur,0);
                    return val[cur];
                } cur=son[cur][1];
            }
        }
    } //找第k大数
    inline void debug(int x){
    	if(!x) return;
    	debug(son[x][0]);
    	writesp(siz[x]);
    	debug(son[x][1]);
	}
    inline int getrnk(int x){ find(x); return siz[son[root][0]]; }
//    inline void erase(int x){
//        ri rig=fixes(x,1),lef=fixes(x,0);
//        splay(rig,0),splay(lef,rig);
//        //此时x位于前驱lef的右儿子且无子树
//        x=son[lef][1]; if(cnt[x]>1) --cnt[x],splay(x,0);
//        else son[lef][1]=0;
//    }
    inline void erase(int x){
        ri rig=fixes(x,1),lef=fixes(x,0);
        splay(lef,0),splay(rig,lef);
        x=son[rig][0]; if(cnt[x]>1) --cnt[x],splay(x,0);
        else son[rig][0]=0;
    }
}; using namespace SplayTree;

int main()
{
    ri n,opt,x; insert(inf),insert(-inf);
    rd(n); while(n--){
        rd(opt),rd(x);
        if(opt==1) insert(x);
        if(opt==2) erase(x);
        if(opt==3) writeln(getrnk(x));
        if(opt==4) writeln(getkth(x+1));
        if(opt==5) writeln(val[fixes(x,0)]);
        if(opt==6) writeln(val[fixes(x,1)]);
    }
    return 0;
}
2022/2/8 10:50
加载中...