题解 P3332 【[ZJOI2013]K大数查询】

· · 题解

此题有三种做法：

1.平衡树套线段树

2.线段树套线段树

3.整体二分

这里介绍一下后两种做法。

我先写了个200+行的线段树套平衡树（注意顺序），然后效率是O(nlog^3n)，简直爆炸。

2.线段树套线段树

为什么线段树套平衡树是O(nlog^3n)的呢？因为我们需要查询的是权值，然而我外层是线段树，所以先二分答案，然后分解区间，到了各个平衡树时，又相当于二分了一次位置，实在是没必要。

因此，这里，我们的线段树套线段树，确切的说应该是权值线段树套区间线段树。

外层是权值线段树，实质上就是一个二分答案的过程，然后运用类似归并树和主席树的思想，我们设询问区间为[ql,qr],答案区间为[l,r],取其mid，然后计算在左儿子[l,mid]和询问区间[ql,qr]中的数的个数，那么我们就可以判断答案是大于mid还是小于mid的了。而在权值线段树的每一个节点上都建一个区间线段树，来维护该权值在[1,n]所有区间上的出现次数，然后维护一个区间和就好了。

还有就是防止MLE，在区间线段树上搞个动态开点就好了。

算法设计基本上就是这样了，具体细节就看代码了。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
#include<ctime>
#define rint register int
using namespace std;
typedef long long ll;
const int inf = 0x7fffffff;
const int N=5e4+5;
const int Tree=N*400;
int n,m,node=0,totn;
int ql[N],qr[N],op[N],b[N],k[N];
int rt[N<<2],tag[Tree];
ll sz[Tree];
struct Tnode{
    int L,R;
}T[Tree];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
#define lc p<<1
#define rc p<<1|1
inline void pushdown(int p,int l,int r){
    int &v=tag[p],mid=(l+r)>>1;
    if (!T[p].L)T[p].L=++node;
    if (!T[p].R)T[p].R=++node;
    tag[T[p].L]+=v,tag[T[p].R]+=v;
    sz[T[p].L]+=v*(mid-l+1),sz[T[p].R]+=v*(r-mid);
    v=0;
}
inline void update(int &p,int ql,int qr,int l=1,int r=n){
    if (!p)p=++node;
    if (ql<=l && r<=qr){
        ++tag[p];sz[p]+=r-l+1;
        return;
    }
    if (tag[p])pushdown(p,l,r);
    rint mid=(l+r)>>1;
    if (ql<=mid) update(T[p].L,ql,qr,l,mid);
    if (mid<qr) update(T[p].R,ql,qr,mid+1,r);
    sz[p]=sz[T[p].L]+sz[T[p].R];
}
inline ll getsum(int &p,int ql,int qr,int l=1,int r=n){
    if (!p)return 0;
    if (ql<=l && r<=qr) return sz[p];
    if (tag[p])pushdown(p,l,r);
    rint mid=(l+r)>>1;
    ll tt=0;
    if (ql<=mid) tt+=getsum(T[p].L,ql,qr,l,mid);
    if (mid<qr) tt+=getsum(T[p].R,ql,qr,mid+1,r);
    return tt;
}
inline void add(int ql,int qr,int k,int p=1,int l=1,int r=totn){
    update(rt[p],ql,qr);
    if (l==r) return;
    rint mid=(l+r)>>1;
    if (k<=mid) add(ql,qr,k,lc,l,mid);
        else add(ql,qr,k,rc,mid+1,r);
}
inline int query(int ql,int qr,ll k,int p=1,int l=1,int r=totn){
    if (l==r) return b[l];
    rint mid=(l+r)>>1;
    ll tt=getsum(rt[rc],ql,qr);
    if (tt<k) return query(ql,qr,k-tt,lc,l,mid);
        else return query(ql,qr,k,rc,mid+1,r);
}
int main(){
    n=read(),m=read();
    for (rint i=1;i<=m;++i){
        op[i]=read(),ql[i]=read(),qr[i]=read(),k[i]=read();
        if (op[i]==1)b[++totn]=k[i];
    }
    sort(b+1,b+totn+1);
    totn=unique(b+1,b+totn+1)-b-1;
    for (rint i=1;i<=m;++i)
        if (op[i]==1)k[i]=lower_bound(b+1,b+totn+1,k[i])-b;
    for (rint i=1;i<=m;++i){
        if (op[i]==1){
            add(ql[i],qr[i],k[i]);
        }else{
            printf("%d\n",query(ql[i],qr[i],k[i]));
        }
    }
    return 0;
}

3.整体二分

这应该属于练整体二分的一道比较基础的题目了。

何谓整体二分？就是直接一起二分所有的询问操作的答案，然后暴力扫描当前操作区间，将其划分为答案的左子区间与右子区间两个部分。

那么以什么为划分依据呢？看看这个操作对于左子区间有没有贡献。如果没有，那么就划分到右子区间中，然后将这个操作的权值更改为这个贡献减去所需的贡献，反之，则划分到左子区间中，同时将这个操作的贡献加入某一个容器，为询问操作服务。

这么说可能有点晕。就这道题说的话，应该是这样：

我们设尚未解决的操作区间为[ql,qr],答案区间为[l,r],令当前答案为mid。

则若该操作是添加操作，如果其添加的C<=mid，这此次操作对于左子区间有贡献，加入左子区间中，并将区间线段树中的区间[q[i].l,q[i].r]整体加1.

反之，则将操作加入到右子区间中。

若该操作是询问操作，如果当前的mid在线段树中查询到的，比它大的数的个数query()>=q[i].k，则证明该询问操作应该在右子区间内可以找到答案。反之，则将q[i].k-=query()，减去此次查询的贡献，然后将询问操作添加到左子区间中。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#define rint register int
using namespace std;
typedef long long ll;
const int N=5e4+5;
struct Ask{
    int op,l,r,id;
    ll v;
}q[N],tl[N],tr[N];
int tag[N<<2],rec[N<<2],ans[N];
ll sum[N<<2];
int n,m,Q;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
#define lc p<<1
#define rc p<<1|1
inline void pushdown(int p,int l,int r){
    if (rec[p]){
        rec[p]=0;
        tag[lc]=tag[rc]=sum[lc]=sum[rc]=0;
        rec[lc]=1,rec[rc]=1;
    }
    if (tag[p]){
        rint mid=(l+r)>>1;
        tag[lc]+=tag[p],tag[rc]+=tag[p];
        sum[lc]+=tag[p]*(mid-l+1);
        sum[rc]+=tag[p]*(r-mid);
        tag[p]=0;
    }
}    
inline void add(int ql,int qr,int w,int p=1,int l=1,int r=n){
    if (ql<=l && r<=qr){
        tag[p]+=w;sum[p]+=w*(r-l+1);
        return;
    }
    if (tag[p] || rec[p])pushdown(p,l,r);
    rint mid=(l+r)>>1;
    if (ql<=mid) add(ql,qr,w,lc,l,mid);
    if (mid<qr) add(ql,qr,w,rc,mid+1,r);
    sum[p]=sum[lc]+sum[rc];
}
inline ll query(int ql,int qr,int p=1,int l=1,int r=n){
    if (ql<=l && r<=qr)return sum[p];
    rint mid=(l+r)>>1;
    ll tt=0;
    if (tag[p] || rec[p])pushdown(p,l,r);
    if (ql<=mid) tt+=query(ql,qr,lc,l,mid);
    if (mid<qr) tt+=query(ql,qr,rc,mid+1,r);
    return tt;
}
inline void solve(int st,int en,int l,int r){
    if (l==r){
        for (rint i=st;i<=en;++i)
            if (q[i].op==2) ans[q[i].id]=l;
        return;
    }
    rint mid=(l+r)>>1;
    bool fl=0,fr=0;
    rint L=0,R=0;
    rec[1]=1;tag[1]=sum[1]=0;
    for (rint i=st;i<=en;++i)
        if (q[i].op==1){
            if (q[i].v>mid){
                add(q[i].l,q[i].r,1);
                tr[++R]=q[i];
            }else
                tl[++L]=q[i];
        }else{
            ll val=query(q[i].l,q[i].r);
            if (val<q[i].v){
                q[i].v-=val;
                fl=1;
                tl[++L]=q[i];
            }else{
                fr=1;
                tr[++R]=q[i];
            }
        }
    for (rint i=1;i<=L;++i) q[st+i-1]=tl[i];
    for (rint i=L+1;i<=L+R;++i) q[st+i-1]=tr[i-L];
    if (fl) solve(st,st+L-1,l,mid);
    if (fr) solve(st+L,en,mid+1,r);
}
int main(){
    n=read(),m=read();
    for (rint i=1;i<=m;++i){
        q[i].op=read(),q[i].l=read(),q[i].r=read(),q[i].v=read();
        if (q[i].op==2)q[i].id=++Q;
    }
    solve(1,m,-n,n);
    for (rint i=1;i<=Q;++i)
        printf("%d\n",ans[i]);
    return 0;
}

貌似一比，树套树还好写一点哈？