此题有三种做法：

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;
}

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

P3332 [ZJOI2013] K大数查询

视频讲解

问题描述

给定N个位置，初始值均为0。有M个操作，每个操作是区间[L, R]加1，或查询区间[L, R]中第K大的数。要求处理这些操作。

解题思路

1. 整体二分：将所有查询和修改操作一起二分答案，对每个mid值判断是否满足条件，逐步缩小范围。
2. 树状数组：维护区间和，支持区间更新（加1）和区间查询（和），用两个树状数组实现区修区查（sum = a*x + b，a和b为树状数组维护的系数）。

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

typedef long long ll;

struct BIT {
    int n;
    vector<ll> tree;
    BIT(int size) : n(size), tree(size + 2, 0) {}
    void update(int idx, ll delta) {
        for (; idx <= n; idx += idx & -idx) tree[idx] += delta;
    }
    ll query(int idx) {
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx) res += tree[idx];
        return res;
    }
};

struct Op {
    int type; // 0: add, 1: query
    int L, R, K, idx;
};

int N, M;
vector<Op> ops;
vector<ll> ans;

// 区间[L, R]加1，查询[L, R]中第K大
void solve(int l, int r, int opL, int opR, vector<Op>& queries) {
    if (opL > opR || l > r) return;
    int mid = (l + r) / 2;
    vector<Op> leftAdd, rightAdd, leftQ, rightQ;
    BIT A(N), B(N); // 维护a*x + b，区间和为a*(R-L+1) + (b[R]-b[L-1])
    for (int i = opL; i <= opR; ++i) {
        Op& op = ops[i];
        if (op.type == 0) { // add
            // 区间[L, R]加1，转化为差分数组更新
            A.update(op.L, 1);
            if (op.R + 1 <= N) A.update(op.R + 1, -1);
            B.update(op.L, op.L);
            if (op.R + 1 <= N) B.update(op.R + 1, -(op.R + 1));
        } else { // query
            // 计算区间[L, R]的和
            auto sum = [&](int x) {
                if (x < 1) return 0LL;
                return A.query(x) * x + B.query(x);
            };
            ll total = sum(op.R) - sum(op.L - 1);
            if (total < op.K) { // 当前mid太小，需更大的数
                op.K -= total;
                rightQ.push_back(op);
            } else { // 当前mid可能是答案，继续二分左半
                leftQ.push_back(op);
            }
        }
    }
    // 记录答案
    for (Op& q : leftQ) {
        if (q.type == 1) ans[q.idx] = mid;
    }
    // 递归处理左右
    solve(l, mid - 1, opL, opL + (leftAdd.size() + leftQ.size()) - 1, leftQ); // 左半查询
    solve(mid + 1, r, opL + leftAdd.size() + leftQ.size(), opR, rightQ); // 右半查询
}

int main() {
    cin >> N >> M;
    ops.resize(M);
    ans.resize(M, 0);
    vector<Op> queries;
    for (int i = 0; i < M; ++i) {
        int type, L, R, K;
        cin >> type >> L >> R >> K;
        if (type == 1) { // 查询
            queries.push_back({1, L, R, K, (int)queries.size()});
        } else { // 修改
            ops[i] = {0, L, R, 0, 0};
        }
    }
    // 合并操作和查询，按操作顺序处理
    for (Op& q : queries) ops[q.idx] = q;
    solve(0, N, 0, M - 1, queries);
    for (ll x : ans) cout << x << '\n';
    return 0;
}

C108 整体二分+树状数组（区修+区查）P3332 [ZJOI2013] K大数查询