替罪羊树

王江睿 · 2023-12-27 22:56:30 · 个人记录

改天写一下正经删除。（惰性删除太傻了）

现在这个删除太蛋疼了。

//非递归替罪羊树
#include<bits/stdc++.h>
using namespace std;
#define getc()(p1==p2&&(p1=buf)==(p2=buf+fread_unlocked(buf,1,1<<21,stdin))?-1:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline void read(int&x){
    x=0;char c,z=0;
    while(!isdigit(c=getc()))z|=c==45;
    do x=x*10+(c^'0'); while(isdigit(c=getc()));
    if(z) x=-x;
}

constexpr double ALPHA=0.767739313;
constexpr int maxN=1.2e6+7;
struct node{
    int v,c,lc,rc,s1,s2,s3;
}tree[maxN];
int nodecnt,ldr[maxN],ldr_cnt;
#define LC tree[x].lc
#define RC tree[x].rc
#define LC$ tree[LC]
#define RC$ tree[RC]

inline void pushup(int x){
    tree[x].s1=LC$.s1+RC$.s1+1;
    tree[x].s2=LC$.s2+RC$.s2+bool(tree[x].c);
    tree[x].s3=LC$.s3+RC$.s3+tree[x].c;
}
inline void dfs(int x){
    if(!x) return;
    dfs(LC);
    if(tree[x].c) ldr[ldr_cnt++]=x;
    dfs(RC);
}
inline void build(int&x,int l,int r){
    if(l==r) return void(x=0);
    int mid=l+r>>1;
    x=ldr[mid];
    build(LC,l,mid);
    build(RC,mid+1,r);
    pushup(x);
}
inline void maintain(int& x){
    pushup(x);
    if(tree[x].s1*ALPHA<max(LC$.s1,RC$.s1)||tree[x].s2<tree[x].s1*ALPHA){
        ldr_cnt=0;
        dfs(x);
        build(x,0,ldr_cnt);
    }
}
int rt,*Q[2*__lg(maxN)]={&rt};
inline void ins(int& i,int k){
    int j=1;
    for(int x=i;x;x=*(Q[j++]=k<tree[x].v?&LC:&RC))
        if(k==tree[x].v) {++tree[x].c;goto mt;}
    tree[*Q[j-1]=++nodecnt]={k,1};
mt: while(j--)
        maintain(*Q[j]);
}
inline void del(int& i,int k){
    int j=1;
    for(int x=i;x;x=*(Q[j++]=k<tree[x].v?&LC:&RC))
        if(k==tree[x].v) {--tree[x].c;goto mt;}
mt: while(j--)
        maintain(*Q[j]);
}
inline int q_rnk(int i,int v){
    int ans=1;
    for(int x=i;x;)
        v<=tree[x].v?x=LC:(ans+=LC$.s3+tree[x].c,x=RC);
    return ans;
}
inline int q_val(int i,int r){
    for(int x=i;x;)
        if(r<=LC$.s3)
            x=LC;
        else if(r>LC$.s3+tree[x].c)
            r-=LC$.s3+tree[x].c,x=RC;
        else return tree[x].v;
    return 0;
}
int main(){
    int n,m,t,x,last=0,ans=0;
    read(n);read(m);
    for (int i=0,j;i<n;++i)
        read(j),ins(rt,j);
    for (int i = 0; i < m; ++i) {
        read(t);read(x);
        x^=last;
        switch(t){
        case 1:
            ins(rt,x);
        continue;case 2:
            del(rt,x);
        continue;case 3:
            ans^=last=q_rnk(rt,x);
        continue;case 4:
            ans^=last=q_val(rt,x);
        continue;case 5:
            ans^=last=q_val(rt,q_rnk(rt,x)-1);
        continue;case 6:
            ans^=last=q_val(rt,q_rnk(rt,x+1));
        }
    }
    printf("%d",ans);
    return 0;
}

9.54s，还是很可以的。

https://www.luogu.com.cn/record/141184381