题解 P3380 【【模板】二逼平衡树（树套树）】

BFqwq · 2019-12-13 13:23:26 · 题解

P3380（树状数组套权值树写法）

直接看标题吧qaq，这不是本题的最优做法其实我觉得是

其实我喜欢叫它动态主席树但是有些大佬不喜欢qaq

为什么我感觉后面的动态主席树题解写的不是很简洁qaq

切入正题

在这儿默认各位已经学过静态主席树了。

（没学过的请跳转P3834）

在静态主席树中，我们了解了线段树的前缀和操作，

以及用一个值出现的次数来开线段树的神奇操作。

那么其实我们的问题只是在于修改而已。

考虑到线段树可以前缀和，

那么其实我们也可以用一些维护前缀和的神奇操作来维护线段树的前缀和，

比如，套一个树状数组或者线段树什么的。

那么，这个数据结构的核心思路就这样子啦~

（注：下文的len是离散化之后的数的个数）

修改

在这里我使用的是树状数组套主席树。

我们都熟悉树状数组的修改方式，

那么我们只要在外层找到需要修改那几棵权值树（或者说是主席树）。

比如我们要修改x号节点，

那么根据树状数组的性质，

我们只需要每次加上lowbit(x)就行啦。

然后进入要修改的主席树，

再按照主席树修改的操作改就结束啦~

code：

int lb(int x){
    return x&(-x);
}
void pushup(int o){
    t[o].v=t[t[o].ls].v+t[t[o].rs].v;
}
void change(int &o,int l,int r,int k,int v){
    if(!o) o=++tot;
    if(l==r){
        t[o].v+=v;
        return ;
    }
    int mid=l+r>>1;
    if(k<=mid) change(t[o].ls,l,mid,k,v);
    else change(t[o].rs,mid+1,r,k,v);
    pushup(o);
}//主席树修改
void add(int o,int v){
    for(int i=o;i<=n;i+=lb(i)) change(rt[i],1,len,a[o],v);
} //树状数组查找修改的树

查询第k小

我们主席树的操作，

就是将第r棵树减去第l-1棵树。

得出我们需要查询的树，

那么这边也是一样的。

假设使用树状数组找到我们要查询的r_1,r_2 \ldots r_k和l_1,l_2 \ldots l_k，

那么我们只需要将所有的r树减去所有的l树，

就能得出我们要的树了。

第k小查询，get~

code：

int query_num(int l,int r,int k){
    if(l==r) {
        return l;
    }
    int mid=l+r>>1,sum=0;
    for(int i=1;i<=cnt;i++) sum+=t[t[tem[i]].ls].v;
    for(int i=1;i<=num;i++) sum-=t[t[tmp[i]].ls].v;
    //同主席树，所有有节点的树减去所有左节点的树
    if(k<=sum){
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].ls;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].ls;
        return query_num(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].rs;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].rs;
        return query_num(mid+1,r,k-sum);
    }
        //注意要所有的节点一起变成子节点
}
int find_num(int l,int r,int k){
    cnt=num=0;
    for(int i=r;i;i-=lb(i)){
        tem[++cnt]=rt[i];
    }//这些是右端点分出来的树
    for(int i=l-1;i;i-=lb(i)){
        tmp[++num]=rt[i];
    }//这些是左端点分出来的树，注意l-1
    return query_num(1,len,k);
} //先用树状数组求出需要查的树

查询排名

这一步操作就显得比较简单。

我们只要把一段区间中小于k的数的个数加起来再加个一就行啦。

具体的操作同查询第k小，

先预处理出需要找的树，

不同的是我们只需要在每棵树中求一个区间和就行啦~

code：

int query_rnk(int l,int r,int k){
    if(l==r) {
        return 0;//注意这里要return 0，因为等于k是不能算进去的
    }
    int mid=l+r>>1,sum=0;
    if(k<=mid){
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].ls;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].ls;
        return query_rnk(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt;i++) sum+=t[t[tem[i]].ls].v,tem[i]=t[tem[i]].rs;
        for(int i=1;i<=num;i++) sum-=t[t[tmp[i]].ls].v,tmp[i]=t[tmp[i]].rs;
        return sum+query_rnk(mid+1,r,k);
    }
}//一个线段树的求和操作，求出1-k-1位置的和
//其实也可以每棵树查一次，在这里我喜欢所有的树一起查
int find_rnk(int l,int r,int k){
    cnt=num=0;
    for(int i=r;i;i-=lb(i)){
        tem[++cnt]=rt[i];
    }
    for(int i=l-1;i;i-=lb(i)){
        tmp[++num]=rt[i];
    }
    return query_rnk(1,len,k)+1;
    //不要忘记加1qaq
}

查询前驱

其实，这个操作我们可以用上面的两个操作来完成。

假设这个数的排名是rk，那么rk-1名的数，是不是就是它的前驱呢~

当然有一个特判：

假设rk已经等于1了，那么就是不存在前驱的情况

那么前驱就这么结束啦~

code：

int find_pri(int l,int r,int k){
    int rk=find_rnk(l,r,k)-1;
    if(rk==0) return 0;
        //因为我前面减一已经减好了，所以特判的时候判是否等于0
    return find_num(l,r,rk);
}

查询后继

其实是一个道理呢~

但是这里就涉及到一个排名是多少的问题。

如果假设后继的排名是rk，

那么k的排名不一定是rk-1，

因为可能有数的排名相同。

其实也没有关系。

我们看到排名操作，其实我们查询排名的时候，

仅仅是查询了小于k的数，然后加了1。

那么其实哪怕这个数不存在，

我们查询排名的时候也不会出问题。

也就是说，我们查询k+1的排名

由于小于等于k的数就是rk-1个

所以返回的排名就一定是rk。

因此，我们只需要查询k+1的排名，

就可以得到其后继的排名。

然后，再查一次第k小就结束啦~

code：

int find_nxt(int l,int r,int k){
    if(k==len) return len+1;
        //为了防止越界，我增加了一个特判
        //要是已经是最大值了，那么它就不可能有后继
    int rk=find_rnk(l,r,k+1);
    if(rk==r-l+2) return len+1;
    return find_num(l,r,rk);
}

复杂度

可以看到，我们任意的一次操作，

都是在树状数组上先查询了一次，

再到线段树上查询了一次，

两个\log加起来，就是n \log ^2 n。

如果是线段树套平衡树的话，

其大部分操作也是这个复杂度，

但是在查询第k小时还要多乘一个\log。

对于空间，其实我们可以发现，

每次修改的时候，我们仅需要改至多\log n棵树，

而每棵树又只要改一条链，所以又是一个log。

于是，空间也是n \log ^2 n级别的复杂度，

完全可以承受。

时间和空间都是上界，

特别是空间，一般的数据根本不可能达到这么高。

然后洛谷的数据又水

完整代码

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=50005;
int len=0;
const int inf=2147483647;
struct seg{
    int v,ls,rs;
}t[maxn*100];
int rt[maxn],n,m,tot,tem[maxn],tmp[maxn],cnt,num;
int lsh[maxn<<1],a[maxn];
struct cz{
    int a,b,c,d;
}q[maxn];
int lb(int x){
    return x&(-x);
}
void pushup(int o){
    t[o].v=t[t[o].ls].v+t[t[o].rs].v;
}
void change(int &o,int l,int r,int k,int v){
    if(!o) o=++tot;
    if(l==r){
        t[o].v+=v;
        return ;
    }
    int mid=l+r>>1;
    if(k<=mid) change(t[o].ls,l,mid,k,v);
    else change(t[o].rs,mid+1,r,k,v);
    pushup(o);
}
void add(int o,int v){
    for(int i=o;i<=n;i+=lb(i)) change(rt[i],1,len,a[o],v);
} 
int query_num(int l,int r,int k){
    if(l==r) {
        return l;
    }
    int mid=l+r>>1,sum=0;
    for(int i=1;i<=cnt;i++) sum+=t[t[tem[i]].ls].v;
    for(int i=1;i<=num;i++) sum-=t[t[tmp[i]].ls].v;
    if(k<=sum){
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].ls;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].ls;
        return query_num(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].rs;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].rs;
        return query_num(mid+1,r,k-sum);
    }
}
int find_num(int l,int r,int k){
    cnt=num=0;
    for(int i=r;i;i-=lb(i)){
        tem[++cnt]=rt[i];
    }
    for(int i=l-1;i;i-=lb(i)){
        tmp[++num]=rt[i];
    }
    return query_num(1,len,k);
} 
int query_rnk(int l,int r,int k){
    if(l==r) {
        return 0;
    }
    int mid=l+r>>1,sum=0;

    if(k<=mid){
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].ls;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].ls;
        return query_rnk(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt;i++) sum+=t[t[tem[i]].ls].v,tem[i]=t[tem[i]].rs;
        for(int i=1;i<=num;i++) sum-=t[t[tmp[i]].ls].v,tmp[i]=t[tmp[i]].rs;
        return sum+query_rnk(mid+1,r,k);
    }
}
int find_rnk(int l,int r,int k){
    cnt=num=0;
    for(int i=r;i;i-=lb(i)){
        tem[++cnt]=rt[i];
    }
    for(int i=l-1;i;i-=lb(i)){
        tmp[++num]=rt[i];
    }
    return query_rnk(1,len,k)+1;
}
int find_pri(int l,int r,int k){
    int rk=find_rnk(l,r,k)-1;
    if(rk==0) return 0;
    return find_num(l,r,rk);
}
int find_nxt(int l,int r,int k){
    if(k==len) return len+1;
    int rk=find_rnk(l,r,k+1);
    if(rk==r-l+2) return len+1;
    return find_num(l,r,rk);
}
signed main(){
        n=read();m=read();
        tot=cnt=num=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            lsh[++len]=a[i];
        }
        for(int i=1;i<=m;i++){
            q[i].a=read();q[i].b=read();q[i].c=read();
            if(q[i].a!=3) q[i].d=read();
            else lsh[++len]=q[i].c;
            if(q[i].a==4 || q[i].a==5) lsh[++len]=q[i].d;
        }
        sort(lsh+1,lsh+len+1);
        len=unique(lsh+1,lsh+len+1)-lsh-1;//离散化
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;
            add(i,1);
        }
        lsh[0]=-inf;
        lsh[len+1]=inf;
            //为了前驱和后继用。
        for(int i=1;i<=m;i++){
            if(q[i].a==3){
                add(q[i].b,-1);
                a[q[i].b]=lower_bound(lsh+1,lsh+1+len,q[i].c)-lsh;
                add(q[i].b,1);
            }
            if(q[i].a==1){
                q[i].d=lower_bound(lsh+1,lsh+1+len,q[i].d)-lsh;
                printf("%d\n",find_rnk(q[i].b,q[i].c,q[i].d));
            }
            if(q[i].a==2){
                printf("%d\n",lsh[find_num(q[i].b,q[i].c,q[i].d)]);
            }
            if(q[i].a==4){
                q[i].d=lower_bound(lsh+1,lsh+1+len,q[i].d)-lsh;
                printf("%d\n",lsh[find_pri(q[i].b,q[i].c,q[i].d)]);
            }
            if(q[i].a==5){
                q[i].d=lower_bound(lsh+1,lsh+1+len,q[i].d)-lsh;
                printf("%d\n",lsh[find_nxt(q[i].b,q[i].c,q[i].d)]);
            }
        }
    return 0;
}

qaq完整的代码就是这样啦~

祝各位WC/NOI/CSP2020加油qaq

要是已经退役的那就祝高考加油吧qaq