关于平衡树模板
查看原帖
关于平衡树模板
371848
吴思诚楼主2023/8/11 16:04
#include<cstdio>
#include<random>
#include<algorithm>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
namespace fstIO{
    const char _fg='\n';
    int _len=0;
    char ibuf[(1<<20)+1],*iS,*iT,_out[(1<<25)+1],_ar[50];
    #define _gh()\
    (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),\
    (iS==iT?EOF:*iS++):*iS++)
    #define putc(ch) _out[_len++]=ch
    void read(){}
    template<typename Type,typename...Types>
    void read(Type&x,Types&...xs){
        x=0;
        char ch=_gh();
        char t=0;
        while(ch<'0'||ch>'9')t|=ch=='-',ch=_gh();
        while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=_gh();
        x=t?-x:x;
        read(xs...);
    }
    template<typename Type>
    void write(Type x){
        int tot=0;
        if(!x)putc('0');
        if(x<0)putc('-'),x=-x;
        while(x)_ar[++tot]=x%10+'0',x/=10;
        for(int i=tot;i;--i)putc(_ar[i]);
        putc(_fg);
    }
    void flush(){
        fwrite(_out,1,_len,stdout);
        _len=0;
    }
}
typedef long long ll;
using namespace fstIO;
const int N=300010;
const ll INF=1e18;
int n,rt,m,l[N],r[N],sz[N],idx,ans[N],c[N];
ll a[N],k[N];
unsigned v[N];
#define up(p) sz[p]=sz[l[p]]+sz[r[p]]+c[p]  
int get(ll key){
    k[++idx]=key;
    sz[idx]=c[idx]=1;
    v[idx]=rd();
    return idx;
}
void zig(int &x){
    int y=l[x];
    l[x]=r[y],r[y]=x,x=y;
    up(r[x]),up(x);
}
void zag(int &x){
    int y=r[x];
    r[x]=l[y],l[y]=x,x=y;
    up(l[x]),up(x);
}
void init(){
    get(-INF),get(INF);
    r[rt=1]=2;
    if(v[1]<v[2])zag(rt);
}
void ins(int &p,int x){
    if(!p)p=get(x);
    else if(k[p]==x)++c[p];
    else if(x<k[p]){
        ins(l[p],x);
        if(v[l[p]]>v[p])zig(p);
    }
    else{
        ins(r[p],x);
        if(v[r[p]]>v[p])zag(p);
    }
    up(p);
}
void del(int &p,int x){
    if(!p)return;
    if(k[p]==x){
        if(c[p]>1)--c[p];
        else if(l[p]||r[p]){
            if(!r[p]||v[l[p]]>v[r[p]]){
                zig(p);
                del(r[p],x);
            }
            else{
                zag(p);
                del(l[p],x);
            }
        }
        else p=0;
    }
    else if(x<k[p])del(l[p],x);
    else del(r[p],x);
    up(p);
}
ll gkey(int p,int x){
    if(!p)return INF;
    if(x<=sz[l[p]])return gkey(l[p], x);
    if(x<=sz[l[p]]+c[p])return k[p];
    return gkey(r[p],x-sz[l[p]]-c[p]);
}
struct query{
    int id,l,r,k;
    bool operator <(const query &A)const{
        return l<A.l;
    }
}q[N];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    read(n,m);
    init();
    E(i, n)read(a[i]);
    E(i, m){
        int l,r,k;
        read(l,r,k);
        q[i]={i,l,r,k};
    }
    sort(q+1,q+1+m);
    int l=1,r=0,cnt=0;
    E(i, m){
        auto[id,L,R,k]=q[i];
        // printf("query:(%d,%d,%d,%d)\n",id,L,R,k);
        while(r<R)ins(rt,a[++r]),++cnt;
        while(l<L)del(rt,a[l++]),--cnt;
        // printf("now size is %d,k=%d\n",cnt,cnt-k+1);
        ans[id]=gkey(rt,k+1);
    }
    E(i, m)write(ans[i]);
    flush();
    return 0;
}

这是一段可以AC本题的代码，由于没有重复元素，那么将表示重复元素个数的 c 数组去掉，得到如下代码：

#include<cstdio>
#include<random>
#include<algorithm>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
namespace fstIO{
    const char _fg='\n';
    int _len=0;
    char ibuf[(1<<20)+1],*iS,*iT,_out[(1<<25)+1],_ar[50];
    #define _gh()\
    (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),\
    (iS==iT?EOF:*iS++):*iS++)
    #define putc(ch) _out[_len++]=ch
    void read(){}
    template<typename Type,typename...Types>
    void read(Type&x,Types&...xs){
        x=0;
        char ch=_gh();
        char t=0;
        while(ch<'0'||ch>'9')t|=ch=='-',ch=_gh();
        while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=_gh();
        x=t?-x:x;
        read(xs...);
    }
    template<typename Type>
    void write(Type x){
        int tot=0;
        if(!x)putc('0');
        if(x<0)putc('-'),x=-x;
        while(x)_ar[++tot]=x%10+'0',x/=10;
        for(int i=tot;i;--i)putc(_ar[i]);
        putc(_fg);
    }
    void flush(){
        fwrite(_out,1,_len,stdout);
        _len=0;
    }
}
typedef long long ll;
using namespace fstIO;
const int N=300010;
const ll INF=1e18;
int n,rt,m,l[N],r[N],sz[N],idx,ans[N];
ll a[N],k[N];
unsigned v[N];
#define up(p) sz[p]=sz[l[p]]+sz[r[p]]+1 
int get(ll key){
    k[++idx]=key;
    sz[idx]=1;
    v[idx]=rd();
    return idx;
}
void zig(int &x){
    int y=l[x];
    l[x]=r[y],r[y]=x,x=y;
    up(r[x]),up(x);
}
void zag(int &x){
    int y=r[x];
    r[x]=l[y],l[y]=x,x=y;
    up(l[x]),up(x);
}
void init(){
    get(-INF),get(INF);
    r[rt=1]=2;
    if(v[1]<v[2])zag(rt);
}
void ins(int &p,int x){
    if(!p)p=get(x);
    else if(x<k[p]){
        ins(l[p],x);
        if(v[l[p]]>v[p])zig(p);
    }
    else{
        ins(r[p],x);
        if(v[r[p]]>v[p])zag(p);
    }
    up(p);
}
void del(int &p,int x){
    if(!p)return;
    if(k[p]==x){
        if(l[p]||r[p]){
            if(!r[p]||v[l[p]]>v[r[p]]){
                zig(p);
                del(r[p],x);
            }
            else{
                zag(p);
                del(l[p],x);
            }
        }
        else p=0;
    }
    else if(x<k[p])del(l[p],x);
    else del(r[p],x);
    up(p);
}
ll gkey(int p,int x){
    if(!p)return INF;
    if(x<=sz[l[p]])return gkey(l[p], x);
    if(x<=sz[l[p]]+1)return k[p];
    return gkey(r[p],x-sz[l[p]]-1);
}
struct query{
    int id,l,r,k;
    bool operator <(const query &A)const{
        return l<A.l;
    }
}q[N];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    read(n,m);
    init();
    E(i, n)read(a[i]);
    E(i, m){
        int l,r,k;
        read(l,r,k);
        q[i]={i,l,r,k};
    }
    sort(q+1,q+1+m);
    int l=1,r=0,cnt=0;
    E(i, m){
        auto[id,L,R,k]=q[i];
        // printf("query:(%d,%d,%d,%d)\n",id,L,R,k);
        while(r<R)ins(rt,a[++r]),++cnt;
        while(l<L)del(rt,a[l++]),--cnt;
        // printf("now size is %d,k=%d\n",cnt,cnt-k+1);
        ans[id]=gkey(rt,k+1);
    }
    E(i, m)write(ans[i]);
    flush();
    return 0;
}
2023/8/11 16:04