CDQ 分治 & 整体二分

Re_FYCCCCTA · 2026-07-04 11:09:41 · 算法·理论

引入

CDQ 分治与整体二分，二者共享“分治”之名，但分治的对象截然不同：CDQ 分治按序列下标分治，整体二分按答案值域分治。前者擅长处理偏序与动态转静态问题，后者擅长处理询问答案可二分的问题。理解这一区别，两套算法的适用场景便一目了然。

Part 1. CDQ 分治

简介

CDQ 分治是一种思想，用于离线高效解决偏序问题。通过将一些问题转化为高维偏序，CDQ 分治能优秀地解决以下两类问题：

优化 1D / 1D 动态规划的转移。
将动态问题转化为静态问题。

:::info[什么是偏序？] 若集合 S 上一个二元关系 \preceq 具有以下三个性质，则称 \preceq 是 S 上的一个偏序，而 S 称为偏序集：

自反性：\forall a\in S,a\preceq a。
反对称性：\forall a,b\in S, (a\preceq b\land b\preceq a)\Rightarrow a=b。
传递性：\forall a,b,c\in S, (a\preceq b\land b \preceq c)\Rightarrow a\preceq c。 :::

基础应用：高维偏序

引入：三维偏序

我们以 P3810 【模板】三维偏序 / 陌上花开为例介绍 CDQ 分治的思想。

题目给定 n 个三元组 (a,b,c)，对于每个元素，需要统计有多少个元素 j 满足 a_j \le a_i,\ b_j \le b_i,\ c_j \le c_i。也就是说，我们定义了如下的偏序关系：

(a_i,b_i,c_i) \preceq (a_j,b_j,c_j) \Longleftrightarrow a_i \le a_j \land b_i \le b_j \land c_i \le c_j

题目要求的就是：对每个点，统计有多少个点在偏序意义下不超过它。

:::info[注意] 如果多个点完全相同，它们彼此之间也有贡献。代码中会将它们合并为一个点并记录出现次数，最后统一加上相同点内部的贡献。 :::

我们先把所有点按 a 排序，这样第一维的偏序关系就被“隐含”在了序列顺序中——左半部分的任何点的 a 都不大于右半部分的任何点的 a（去重后严格成立）。

对于当前分治区间 [l,r]，设中点为 mid。所有“贡献点 i 在左半，受贡点 j 在右半”的点对，天然满足 a_i \le a_j。于是，整个问题的点对贡献可以分成三类：

把区间分为 [l,mid] 和 [mid+1,r] 两部分，这样 1、3 类的点对分别完全包含在这两个区间内，递归下去处理，现在只处理 2 类点对的贡献（如果你把 CDQ 分治的递归树画出来，你会发现它就是一颗线段树！）。

这就是 CDQ 分治的核心思想——每层只处理跨中点的贡献，递归解决区间内部。

现在集中处理第 3 类。此时要处理的点对满足 i \in [l,mid],\ j \in [mid+1,r]，且第一维 a 已经天然有序。

我们把左右区间分别按 b 排序，然后用双指针扫描：枚举右区间的每个点 j，指针 i 从左区间开头向右移动，将所有满足 b_i \le b_j 的点 i 的第三维 c_i 插入树状数组。由于左右区间都已按 b 升序排列，指针 i 随着 j 的右移单调不降。

此时，树状数组中维护的就是所有“第一维 a 在左、第二维 b 不超过当前点”的点。查询树状数组中 c \le c_j 的前缀和，就得到了当前点 j 从左侧获得的贡献。

至此，三维偏序完美解决。时间复杂度满足：

T(n) = 2T(n/2) + O(n\log n) = O(n\log^2 n)

空间复杂度为 O(n)。

:::info[小优化] 不必每次都对左右区间重新按 b 排序，可以在分治过程中模仿归并排序，将两个已按 b 有序的子区间合并，这样不改变整体时间复杂度，但是能显著降低常数。

在这道题中不加优化比加优化慢了一倍多。 :::

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define endl '\n'
const int N=1e5+5;
const int V=2e5+5;
int m,n,mx;
struct Node{int x,y,z,cnt,res;}a[N];
int ans[N];
array<int,3> tmp[N];
struct BIT{
    #define lb (p&-p)
    int t[V];
    void upd(int p,int k){for(;p<=mx;p+=lb) t[p]+=k;}
    int qry(int p){int res=0; for(;p;p-=lb) res+=t[p]; return res;}
    #undef lb
}T;
bool cmp(Node a,Node b){return a.y==b.y?a.z<b.z:a.y<b.y;}
Node t[N];
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    int i,j,k;
    for(i=k=l,j=mid+1; j<=r; j++){
        for(; i<=mid&&a[i].y<=a[j].y; i++){
            T.upd(a[i].z,a[i].cnt);
            t[k++]=a[i];
        }
        a[j].res+=T.qry(a[j].z);
        t[k++]=a[j];
    }
    FOR(p,l,i-1) T.upd(a[p].z,-a[p].cnt);
    for(; i<=mid; i++) t[k++]=a[i];
    FOR(i,l,r) a[i]=t[i];
}
int main(){
    CLOSE_TIE
    cin>>m>>mx;
    FOR(i,1,m) cin>>tmp[i][0]>>tmp[i][1]>>tmp[i][2];
    sort(tmp+1,tmp+m+1);
    FOR(i,1,m)
        if(tmp[i][0]!=tmp[i-1][0]||tmp[i][1]!=tmp[i-1][1]||tmp[i][2]!=tmp[i-1][2]){
            a[++n]={tmp[i][0],tmp[i][1],tmp[i][2],1,0};
        }else{
            ++a[n].cnt;
        }
    cdq(1,n);
    FOR(i,1,n) ans[a[i].res+a[i].cnt-1]+=a[i].cnt;
    FOR(i,0,m-1) cout<<ans[i]<<endl;
    return 0;
}

:::

以上就是 CDQ 分治的思想。它的核心是“每层只处理跨中点的贡献，递归解决区间内部”。而处理跨中点的贡献，就是我们要着重考虑的地方：利用分治结构带来的“左区间天然优于右区间”的顺序，把高维限制转化为分治结构带来的天然顺序，从而在合并时用数据结构消去剩余维度。

回忆归并排序求逆序对（二维偏序）的过程，会发现它和 CDQ 分治非常相似！它也可以看作 CDQ 分治的应用。

CDQ 套 CDQ：四维偏序

例题：P14957 【模板】离线静态四维数点

四维偏序比三维多一个维度，一重 CDQ 不够用了，需要再套一层。

外层 CDQ 对第一维分治。合并时，把左半区间的点打上 flag=0，右半区间的点打上 flag=1，传给内层 CDQ。

内层 CDQ 在这个区间上对第二维分治，处理剩下的两维。唯一不同的是：插入树状数组时只插 flag=0 的点，查询时只查 flag=1 的点。这样就保证了贡献只从“外层左边”向“外层右边”传递。

时间复杂度：O(n \log^3 n)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define endl '\n'
const int N=4e5+5;
const int V=N<<3;
int n,m,ans[N];
int b[V],bc;
struct Node{int x,y,s,t,id; bool f,fl;}a[N<<1];
struct BIT{
    #define lb (p&-p)
    int t[V];
    inline void upd(int p,int k){for(;p;p-=lb) t[p]+=k;}
    inline int qry(int p){int res=0; for(;p<=bc;p+=lb) res+=t[p]; return res;}
    #undef lb
}T;
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
inline bool cmpx(Node a,Node b){return a.x<b.x;}
inline bool cmpy(Node a,Node b){return a.y<b.y;}
inline bool cmps(Node a,Node b){return a.s>b.s;}
Node tmp[N<<1];
void cdq2(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    stable_sort(a+l,a+r+1,cmpy);
    cdq2(l,mid), cdq2(mid+1,r);
    int i,j,p;
    for(i=p=l,j=mid+1; j<=r; j++){
        for(; i<=mid&&a[i].s>=a[j].s; i++){
            if(!a[i].fl) T.upd(a[i].t,a[i].f);
            tmp[p++]=a[i];
        }
        if(a[j].fl) ans[a[j].id]+=T.qry(a[j].t)*(a[j].f^1);
        tmp[p++]=a[j];
    } FOR(k,l,i-1) if(!a[k].fl) T.upd(a[k].t,-a[k].f);
    for(; i<=mid; i++) tmp[p++]=a[i];
    FOR(k,l,r) a[k]=tmp[k];
}
void cdq1(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    stable_sort(a+l,a+r+1,cmpx);
    cdq1(l,mid), cdq1(mid+1,r);
    FOR(i,l,mid) a[i].fl=0;
    FOR(i,mid+1,r) a[i].fl=1;
    cdq2(l,r);
}
int main(){
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,n){
        cin>>a[i].x>>a[i].y>>a[i].s>>a[i].t;
        b[++bc]=a[i].x,b[++bc]=a[i].y,b[++bc]=a[i].s,b[++bc]=a[i].t;
        a[i].f=1;
    }
    FOR(i,n+1,n+m){
        cin>>a[i].x>>a[i].y>>a[i].s>>a[i].t;
        b[++bc]=a[i].x,b[++bc]=a[i].y,b[++bc]=a[i].s,b[++bc]=a[i].t;
        a[i].f=0,a[i].id=i-n;
    } n+=m;
    sort(b+1,b+bc+1);
    bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n) a[i].x=get(a[i].x),a[i].y=get(a[i].y),a[i].s=get(a[i].s),a[i].t=get(a[i].t);
    cdq1(1,n);
    FOR(i,1,m) cout<<ans[i]<<endl;
    return 0;
}

:::

:::warning[实现细节]{open}

或许你注意到了我的这两份代码的差异：一份使用普通的 sort 并合并重复点，另一份使用稳定排序 stable_sort 但未做合并。两种做法都是在解决同一个问题：CDQ 分治中相同元素之间的贡献如何正确计算。

这个问题有两种解决思路：

方案一：sort + 手动去重。将所有完全相同的点合并成一个点，并且保证比较器是严格全序——主关键字相等时继续比较次关键字，直到能区分任意两个元素为止。优点是速度快、空间小；缺点是需要额外处理去重逻辑。
方案二：stable_sort + 不去重。stable_sort 能保证相等元素的相对顺序与输入时一致。优点是写代码方便；缺点是 stable_sort 需要额外的 O(n) 空间，且当内存不足时会退化为 O(n\log^2 n)，时间和空间开销都更大。 :::

优化 1D / 1D 动态规划的转移

1D/1D 动态规划 指状态一维、决策一维的转移方程（如 f_i = \max_{j<i}\{f_j + ...\}）。朴素转移是 O(n^2) 的，当决策点 j 对 i 的贡献满足偏序关系时，CDQ 分治可以将这些决策批量处理，从而高效处理。

这类问题在写的时候有一个重要的细节：处理跨中点的贡献要夹在向左递归和向右递归之间，即中序遍历整个递归树。因为在计算某个位置的 dp 值时，能转移到它的位置一定要是计算好的（即在它之前的所有位置）。

例题

P3364 Cool loves touli

容易列出 dp 转移为：

f_i=\max_{l_j<l_i\land a_j\le s_i\land w_j\le a_i} f_j + 1

转移是三维偏序的形式，然后就是打一遍模板了。这里我们只需要求前缀 \max，也可以用树状数组。

时间复杂度：O(n\log^2 n)。

P3769 [CH弱省胡策R2] TATT

上题的四维版，CDQ 套 CDQ 优化 dp 即可。

时间复杂度：O(n\log^3 n)。

双倍经验：P5621 [DBOI2019] 德丽莎世界第一可爱。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai4=array<int,4>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define endl '\n'
const int N=5e4+5;
const int V=2e5+5;
int n,m;
ai4 t[N];
int bc,b[V];
struct Node{
    int a,b,c,d,cnt,dp;
    bool fl;
}p[N];
struct BIT{
    #define lb (p&-p)
    int t[V];
    void cl(int p){for(;p<=bc;p+=lb) t[p]=0;}
    void upd(int p,int k){for(;p<=bc;p+=lb) t[p]=max(t[p],k);}
    int qry(int p){int res=0; for(;p;p-=lb) res=max(res,t[p]); return res;}
}T;
bool cmpa(Node x,Node y){return x.a==y.a?x.b==y.b?x.c==y.c?x.d<y.d:x.c<y.c:x.b<y.b:x.a<y.a;}
bool cmpb(Node x,Node y){return x.b==y.b?x.c==y.c?x.d==y.d?x.a<y.a:x.d<y.d:x.c<y.c:x.b<y.b;}
bool cmpc(Node x,Node y){return x.c==y.c?x.d==y.d?x.a==y.a?x.b<y.b:x.a<y.a:x.d<y.d:x.c<y.c;}
void cdq2(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    sort(p+l,p+r+1,cmpb);
    cdq2(l,mid);
    sort(p+l,p+mid+1,cmpc); sort(p+mid+1,p+r+1,cmpc);
    int i,j; for(i=l,j=mid+1; j<=r; j++){
        for(; i<=mid&&p[i].c<=p[j].c; i++){
            if(!p[i].fl) T.upd(p[i].d,p[i].dp);
        }
        if(p[j].fl) p[j].dp=max(p[j].dp,T.qry(p[j].d)+p[j].cnt);
    }FOR(k,l,i-1) if(!p[k].fl) T.cl(p[k].d);
    cdq2(mid+1,r);
}
void cdq1(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    sort(p+l,p+r+1,cmpa);
    cdq1(l,mid);
    FOR(i,l,mid) p[i].fl=0;
    FOR(i,mid+1,r) p[i].fl=1;
    cdq2(l,r);
    sort(p+l,p+r+1,cmpa);
    cdq1(mid+1,r);
}
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
int main(){
    CLOSE_TIE
    cin>>m;
    FOR(i,1,m){
        cin>>t[i][0]>>t[i][1]>>t[i][2]>>t[i][3];
        b[++bc]=t[i][0],b[++bc]=t[i][1],b[++bc]=t[i][2],b[++bc]=t[i][3];
    }
    sort(t+1,t+m+1);
    sort(b+1,b+bc+1);
    bc=unique(b+1,b+bc+1)-b-1;
    p[++n]={get(t[1][0]),get(t[1][1]),get(t[1][2]),get(t[1][3]),1,1,0};
    FOR(i,2,m){
        if(t[i][0]!=t[i-1][0] || t[i][1]!=t[i-1][1] || t[i][2]!=t[i-1][2] || t[i][3]!=t[i-1][3])
            p[++n]={get(t[i][0]),get(t[i][1]),get(t[i][2]),get(t[i][3]),1,1,0};
        else p[n].cnt++,p[n].dp++;
    }
    cdq1(1,n);
    int ans=0; FOR(i,1,n) ans=max(ans,p[i].dp);
    cout<<ans<<endl;
    return 0;
}

:::

P2487 [SDOI2011] 拦截导弹

题目给出了一个三维偏序关系，我们把偏序集用图表示出来（Hasse 图），这个图一定是 DAG，我们需要求 DAG 上最长链和它的个数，以及经过某个点的最长链数量。

用四个 dp 数组 f_i,F_i,g_i,G_i 分别表示以某个点结尾的最长链长度及方案数和以某个点开头的最长链长度及方案数。则最长链长度 l=\max_i f_i，最长链个数就是 t=\sum_{f_i=l}F_i。点 i 在某条最长链里等价于 f_i+g_i-1=l，经过它的最长链数量就是 F_i\times G_i。

时间复杂度：O(n\log^2 n)。

这题写起来有点困难……你需要两次 cdq 分别转移以某个点为开头和结尾的 dp 值，然后树状数组需要维护最大值及个数。

我的代码太丑陋了，就不放了……

将动态问题转化为静态问题

许多动态问题——天然带有一个隐式的维度：时间。如果我们将每个操作都看作一个点，那么“修改对查询产生影响”当且仅当修改时间早于查询时间。于是，可以将时间维度就纳入偏序集中，动态问题转化为静态的高维偏序问题。

转化后的偏序维度通常包括：

时间维：操作发生的先后顺序。
空间维：修改/查询涉及的位置、值等。
贡献系数：修改对答案的贡献可能是正的（加入元素）或负的（删除元素）。

CDQ 分治的作用就是处理这些维度之间的偏序关系。值得注意的是，由于“未来”的修改不能影响“过去”的查询，我们在分治时需要先递归左区间处理内部贡献，再统计左区间对右区间的跨区间贡献，最后递归右区间——也就是中序遍历整个分治树。这与 DP 优化章节中提到的顺序一致。

例题

P4390 [BalkanOI 2007] Mokia 摩基亚

加入时间维后，对于一个询问 i，就相当于问有多少个点 j 满足 t_j<t_i\land x_{1i}\le x_j\le x_{2i}\land y_{1i}\le y_j\le y_{2i}。这里不必将后两个条件拆成四个矩形，因为在处理最里层时，树状数组可以支持区间查询，于是拆成两个即可。

时间复杂度：O(n\log^2 n)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int V=2e6+5;
const int N=160005;
const int M=10005;
int w,n,ans[N+M];
struct Node{int x,y,zl,zr,k; bool t;}a[N+(M<<1)];
struct BIT{
    #define lb (p&-p)
    int t[V];
    void upd(int p,int k){for(++p;p<=w+1;p+=lb) t[p]+=k;}
    int qry(int p){int res=0; for(++p;p;p-=lb) res+=t[p]; return res;}
    #undef lb
}T;
Node tmp[N+(M<<1)];
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid), cdq(mid+1,r);
    int i,j,p;
    for(i=p=l,j=mid+1; j<=r; j++){
        for(; i<=mid&&a[i].y<=a[j].y; i++){
            if(!a[i].t) T.upd(a[i].zl,a[i].k);
            tmp[p++]=a[i];
        }
        if(a[j].t) ans[a[j].x]+=(T.qry(a[j].zr)-T.qry(a[j].zl-1))*a[j].k;
        tmp[p++]=a[j];
    } FOR(k,l,i-1) if(!a[k].t) T.upd(a[k].zl,-a[k].k);
    for(; i<=mid; i++) tmp[p++]=a[i];
    FOR(k,l,r) a[k]=tmp[k];
}
int main(){
    CLOSE_TIE
    int op; cin>>op>>w;
    vector<int> q;
    for(int i=1; ;i++){
        cin>>op;
        if(op==3) break;
        int x,y,s,t;
        if(op==1){
            cin>>x>>y>>s;
            a[++n]={i,x,y,y,s,0};
        }else{
            cin>>x>>y>>s>>t;
            a[++n]={i,s,y,t,1,1};
            a[++n]={i,x-1,y,t,-1,1};
            q.psbk(i);
        }
    }
    cdq(1,n);
    for(int i:q) cout<<ans[i]<<endl;
    return 0;
}

:::

P3157 [CQOI2011] 动态逆序对

设 t_i 表示 a_i 被删除的时间。则对于逆序对 (i,j)，其能够对 [1,\min\{t_i,t_j\}] 时刻的答案做出贡献。拆一下就有：

直接 CDQ 分治即可。

时间复杂度：O(n\log^2 n)。

升级版：P12685 [国家集训队] 排队加强版。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define endl '\n'
const int N=1e5+5;
int n,m;
struct Node{int x,y,z;}a[N];
bool cmp1(Node a,Node b){return a.y==b.y? a.z>b.z : a.y>b.y;}
bool cmp2(Node a,Node b){return a.y==b.y? a.z>b.z : a.y<b.y;}
struct BIT{
    #define lb (p&-p)
    ll t[N],n;
    void upd(int p,ll k){++p; for(;p<=n+1;p+=lb) t[p]+=k;}
    ll qry(int p){
        ++p; if(!p) return 0;
        ll res=0; for(;p;p-=lb) res+=t[p]; return res;
    }
    #undef lb
}T;
ll ans[N];
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid), cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp1); sort(a+mid+1,a+r+1,cmp1);
    int i,j; for(i=l,j=mid+1; i<=mid; i++){
        for(; j<=r&&a[i].y<a[j].y; j++){
            T.upd(a[j].z,1);
        }
        int qwq=T.qry(a[i].z-1);
        ans[a[i].x-1]+=qwq;
    }
    FOR(k,mid+1,j-1) T.upd(a[k].z,-1);

    sort(a+l,a+mid+1,cmp2); sort(a+mid+1,a+r+1,cmp2);
    for(i=l,j=mid+1; i<=mid; i++){
        for(; j<=r&&a[i].y>a[j].y; j++){
            T.upd(a[j].z,1);
        }
        int qwq=T.qry(n)-T.qry(a[i].z);
        ans[a[i].x-1]+=qwq;
    }
    FOR(k,mid+1,j-1) T.upd(a[k].z,-1);
}
int pos[N];
int main(){
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,n) cin>>a[i].z, a[i].y=i,a[i].x=m+1, pos[a[i].z]=i;
    FOR(i,1,m){
        int b; cin>>b;
        a[pos[b]].x=i;
    }
    sort(a+1,a+n+1,[](Node a,Node b){
         return a.x==b.x?a.y==b.y? a.z>b.z : a.y<b.y : a.x<b.x;
    });
    T.n=n;
    cdq(1,n);
    REV(i,m,0) ans[i]+=ans[i+1];
    FOR(i,0,m-1) cout<<ans[i]<<endl;
    return 0;
}

:::

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

要求统计本质不同逆序对数量，这个直接放在序列上做很困难，考虑从值域的角度解决。我们设 f_x,l_x 分别表示 x 在序列中第一次出现和最后一次的位置，则 (x,y) 能对答案作出贡献当且仅当 x>y\land f_x<l_x。每一次修改对 f_x,l_x 的变化数量是 O(1) 的，这个可以用 set 维护每种数字出现的位置维护。

考虑计算每次修改对答案的贡献（它对修改的时刻及之后所有时刻的答案都有贡献），修改可以看作一个五元组 (t,x,0/1,y,k)，表示表示在 t 时刻，将 f_x 或 l_x 修改为 y，且贡献系数为 k（k\in\{1,-1\}）。则有：

k\sum_{(t',x',1,y',k')} k' [t'<t\land x>x'\land y<y']

k\sum_{(t',x',0,y',k')} k'[t'<t\land x'>x\land y'<y]

这是一个三维偏序，使用 CDQ 分治以保证空间线性。时间复杂度：O(n\log^2 n)。

如果你的时间被卡了，请注意不要创建过多无用修改（只在 f_x,l_x 改变时修改才有意义）。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define endl '\n'
const int N=1e5+5;
int n,m,a[N],fir[N],ed[N],Q;
ll ans[N];
struct Node{
    //(x,y,t,z,k)，把 x 的 fir/ed 改为 y，在 z 时刻，贡献系数为 k
    int x,y,z,k;
    bool t;
}b[(N<<3)+(N<<1)];
struct BIT{
    #define lb (p&-p)
    int t[N];
    void upd(int p,int k){++p; for(;p<=n+2;p+=lb) t[p]+=k;}
    int qry(int p){
        ++p;
        int res=0; for(;p;p-=lb) res+=t[p]; return res;
    }
}T;
set<int> pos[N];
inline bool cmp1(const Node &a,const Node &b){return a.x<b.x;}
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid), cdq(mid+1,r);

    sort(b+l,b+mid+1,cmp1); sort(b+mid+1,b+r+1,cmp1);
    int i,j; for(i=l,j=mid+1; j<=r; j++){
        for(; i<=mid&&b[i].x<b[j].x; i++){
            if(b[i].t) T.upd(b[i].y,b[i].k);
        }
        if(!b[j].t) ans[b[j].z]+=b[j].k*(T.qry(n)-T.qry(b[j].y));
    } FOR(k,l,i-1) if(b[k].t) T.upd(b[k].y,-b[k].k);

    for(i=mid,j=r; j>mid; j--){
        for(; i>=l&&b[i].x>b[j].x; i--){
            if(!b[i].t) T.upd(b[i].y,b[i].k);
        }
        if(b[j].t) ans[b[j].z]+=b[j].k*T.qry(b[j].y-1);
    } FOR(k,i+1,mid) if(!b[k].t) T.upd(b[k].y,-b[k].k);
}
int main(){
    CLOSE_TIE
    cin>>n;
    FOR(i,1,n) cin>>a[i], pos[a[i]].insert(i);
    FOR(i,1,n){
        if(pos[i].empty()) fir[i]=n+1,ed[i]=0;
        else fir[i]=*pos[i].begin(),ed[i]=*pos[i].rbegin();
        b[++m]={i,fir[i],0,1,0};
        b[++m]={i,ed[i],0,1,1};
    }
    cin>>Q;
    FOR(i,1,Q){
        int x,y; cin>>x>>y;
        pos[a[x]].erase(x); pos[y].insert(x);
        int firx,edx;
        if(pos[a[x]].empty()) firx=n+1, edx=0;
        else firx=*pos[a[x]].begin(), edx=*pos[a[x]].rbegin();
        if(firx!=fir[a[x]]){
            b[++m]={a[x],fir[a[x]],i,-1,0};
            b[++m]={a[x],fir[a[x]]=firx,i,1,0};
        }
        if(edx!=ed[a[x]]){
            b[++m]={a[x],ed[a[x]],i,-1,1};
            b[++m]={a[x],ed[a[x]]=edx,i,1,1};
        }

        int firy=*pos[y].begin(), edy=*pos[y].rbegin();
        if(firy!=fir[y]){
            b[++m]={y,fir[y],i,-1,0};
            b[++m]={y,fir[y]=firy,i,1,0};
        }
        if(edy!=ed[y]){
            b[++m]={y,ed[y],i,-1,1};
            b[++m]={y,ed[y]=edy,i,1,1};
        }
        a[x]=y;
    }
    cdq(1,m);
    FOR(i,0,Q){
        cout<<ans[i]<<endl;
        ans[i+1]+=ans[i];
    }
    return 0;
}

:::

Part 2. 整体二分

简介

顾名思义，整体二分就是当一个问题有多个询问，且询问都可以用二分解决时，如果每个询问都分别进行一次二分会 TLE，我们可以选择把询问离线下来，把所有询问统一进行二分。

基础应用：区间第 k 小

引入：静态区间第 k 小

我们以 P3834 【模板】可持久化线段树 2 为例介绍整体二分。

对于一个询问，一个可行的二分方法是对值域二分，每次检查有多少个 \le mid 数的在询问的区间内。我们考虑把这种方法一次性应用到所有询问上。

对于值域区间 [L,R]，我们记我们维护一个操作序列，包含所有值落在该值域内的初始元素（可以看作修改操作），以及答案确定在该区间内的询问。把这个区间内所有 \le mid := \frac{(L+R)}2 的数的位置（不是值）全部插入树状数组中，然后对询问 (l,r,k) 在树状数组上查询有多少个 \le mid 的数的位置在 [l,r] 内，记这个数量为 c，这会有两种情况：

边界是 L=R，这时这些询问的答案就是 L。

时间复杂度为 O((n+m)\log^2 n)，具体见下：

整体二分按值域折半，从而递归深度为 O(\log n)。每一层所有子问题扫描的操作总数是 O(n+m)，且每个操作需执行一次树状数组，故每层代价为 O((n+m)\log n)。于是总计为 O(\log n) \times O((n+m)\log n) = O((n+m)\log^2 n)。

空间复杂度为 O(n)。

我们可以进一步优化到 1log：

把区间查询拆成两个前缀查询，将元素和查询的端点排序，每次递归做保序分裂，每层线性扫描归并出贡献，去掉树状数组的 \log，总复杂度 O((n+m)\log n)。

这需要保序分裂和全局排序，常数较大。在 2\times 10^5 数据下，理论更优但实际跑得比树状数组整体二分慢约 1s。

:::success[2log 代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=2e5+5;
int n,m,a[N],cnt,ans[N];
int b[N],bc;
struct Qu{int l,r,k,id; bool t;}q[N<<1];
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
struct BIT{
    #define lb (p&-p)
    int t[N];
    void clr(int p){for(;p<=n;p+=lb) if(!t[p]) return; else t[p]=0;}
    void upd(int p,int k){for(;p<=n;p+=lb) t[p]+=k;}
    int qry(int p){
        if(!p) return 0;
        int res=0; for(;p;p-=lb) res+=t[p]; return res;
    }
    #undef lb
}T;
Qu q1[N<<1],q2[N<<1];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr)
            if(q[i].t) ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    FOR(i,ql,qr){
        if(!q[i].t){
            if(q[i].l<=mid){
                T.upd(q[i].id,1);
                q1[++cnt1]=q[i];
            }else{
                q2[++cnt2]=q[i];
            }
        }else{
            int qwq=T.qry(q[i].r)-T.qry(q[i].l-1);
            if(q[i].k<=qwq){
                q1[++cnt1]=q[i];
            }else{
                q[i].k-=qwq;
                q2[++cnt2]=q[i];
            }
        }
    }
    FOR(i,1,cnt1)
        if(!q1[i].t) T.clr(q1[i].id);
    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
int main(){
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,n) cin>>a[i], b[++bc]=a[i];
    sort(b+1,b+bc+1); bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n){
        a[i]=get(a[i]);
        q[++cnt]={a[i],a[i],0,i,0};
    }
    FOR(i,1,m){
        ++cnt;
        cin>>q[cnt].l>>q[cnt].r>>q[cnt].k;
        q[cnt].id=i, q[cnt].t=1;
    }
    solve(1,bc,1,cnt);
    FOR(i,1,m) cout<<b[ans[i]]<<endl;
    return 0;
}

:::

:::success[1log 代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=2e5+5;
int n,m,a[N],K[N],cnt,ans[N];
int b[N],bc;
struct Qu{int p,id,t;}q[N*3];
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
int sum[N*3];
short bel[N],pbel[N];
Qu q1[N*3],q2[N*3];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr)
            if(q[i].t) ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0,cur=0;
    FOR(i,ql,qr){
        if(!q[i].t){
            if(a[q[i].p]<=mid) ++cur,pbel[q[i].id]=1;
            else pbel[q[i].id]=2;
        }else{
            sum[q[i].id]+=q[i].t*cur;
        }
    }
    FOR(i,ql,qr)
        if(q[i].t==1){
            int id=q[i].id;
            if(K[id]<=sum[id]) bel[id]=1;
            else K[id]-=sum[id],bel[id]=2;
        }
    FOR(i,ql,qr){
        if(q[i].t){
            if(bel[q[i].id]==1) q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }else{
            if(pbel[q[i].id]==1) q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    FOR(i,ql,qr){
        if(q[i].t) bel[q[i].id]=sum[q[i].id]=0;
        else pbel[q[i].id]=0;
    }
    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,n) cin>>a[i], b[++bc]=a[i];
    sort(b+1,b+bc+1); bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n){
        a[i]=get(a[i]);
        q[++cnt]={i,i,0};
    }
    FOR(i,1,m){
        int l,r; cin>>l>>r>>K[i];
        q[++cnt]={l-1,i,-1};
        q[++cnt]={r,i,1};
    }
    sort(q+1,q+cnt+1,[](Qu a,Qu b){
        return a.p==b.p?(!a.t)?1:0:a.p<b.p;
    });
    solve(1,bc,1,cnt);
    FOR(i,1,m) cout<<b[ans[i]]<<endl;
    return 0;
}

:::

带修区间第 k 小

P2617 Dynamic Rankings

如果用整体二分写，几乎与上题 2log 做法没有区别，就把修改拆成先删除后增加计入操作内即可。

但是如果使用数据结构维护，就会变得很复杂，虽然时间复杂度与整体二分同为 O(n\log^2 n)，但常数比整体二分大很多，且空间复杂度不如整体二分的线性，更不用说编码更困难了。

这里不能沿用静态区间第 k 小的 1log 做法，因为修改时间带有时间顺序，不能根据端点排序。

时间复杂度：O(n\log^2 n)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=1e5+5;
int n,m,a[N],cnt,Qcnt,ans[N];
int b[N<<1],bc;
struct Qu{int l,r,k,id; bool t;}q[N*3];
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
struct QWQ{char c; int l,r,k;}tmp[N];
struct BIT{
    #define lb (p&-p)
    int t[N];
    void upd(int p,int k){for(;p<=n;p+=lb) t[p]+=k;}
    int qry(int p){
        if(!p) return 0;
        int res=0; for(;p;p-=lb) res+=t[p];
        return res;
    }
    #undef lb
}T;
Qu q1[N*3],q2[N*3];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr){
            if(q[i].t) ans[q[i].id]=l;
        }
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    FOR(i,ql,qr){
        if(!q[i].t){
            if(q[i].l<=mid){
                T.upd(q[i].id,q[i].k);
                q1[++cnt1]=q[i];
            }else{
                q2[++cnt2]=q[i];
            }
        }else{
            int qwq=T.qry(q[i].r)-T.qry(q[i].l-1);
            if(q[i].k<=qwq){
                q1[++cnt1]=q[i];
            }else{
                q[i].k-=qwq;
                q2[++cnt2]=q[i];
            }
        }
    }
    FOR(i,1,cnt1)
        if(!q1[i].t) T.upd(q1[i].id,-q1[i].k);
    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
int main(){
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,n) cin>>a[i], b[++bc]=a[i];
    FOR(i,1,m){
        cin>>tmp[i].c>>tmp[i].l>>tmp[i].r;
        if(tmp[i].c=='Q') cin>>tmp[i].k;
        else b[++bc]=tmp[i].r;
    }
    sort(b+1,b+bc+1); bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n){
        a[i]=get(a[i]);
        q[++cnt]={a[i],a[i],1,i,0};
    }
    FOR(i,1,m){
        auto [c,l,r,k]=tmp[i];
        if(c=='Q') q[++cnt]={l,r,k,++Qcnt,1};
        else{
            q[++cnt]={a[l],a[l],-1,l,0};
            a[l]=r=get(r);
            q[++cnt]={r,r,1,l,0};
        }
    }
    solve(1,bc,1,cnt);
    FOR(i,1,Qcnt) cout<<b[ans[i]]<<endl;
    return 0;
}

:::

例题

P1527 [国家集训队] 矩阵乘法

与区间第 k 小唯一不同的是：对矩阵内的每个数，我们要往一个二维平面上插入一个点；对询问，我们要查询矩形和。可以使用多种方式维护，下面给出两种方式：

二维树状数组维护。时间复杂度 O((n^2+q)\log^3 n)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=505;
const int QQ=6e4+5;
int n,Q,a[N][N],cnt,ans[QQ];
int b[N*N],bc;
struct Qu{int lx,ly,rx,ry,k,id;}q[QQ+N*N];
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
struct BIT{
    #define lb(p) (p&-p)
    int t[N][N];
    inline void upd(int p,int qq,int k){
        for(;p<=n;p+=lb(p))
            for(int q=qq;q<=n;q+=lb(q)) t[p][q]+=k;
    }
    inline int qry(int p,int qq){
        if(!p||!qq) return 0;
        int res=0;
        for(;p;p-=lb(p))
            for(int q=qq;q;q-=lb(q)) res+=t[p][q];
        return res;
    }
    inline int qry(int lx,int ly,int rx,int ry){
        return qry(rx,ry)-qry(lx-1,ry)-qry(rx,ly-1)+qry(lx-1,ly-1);
    }
    #undef lb(p)
}T;
Qu q1[QQ+N*N],q2[QQ+N*N];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr)
            if(q[i].id) ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    FOR(i,ql,qr){
        if(!q[i].id){
            if(q[i].k<=mid){
                T.upd(q[i].lx,q[i].ly,1);
                q1[++cnt1]=q[i];
            }else{
                q2[++cnt2]=q[i];
            }
        }else{
            int cur=T.qry(q[i].lx,q[i].ly,q[i].rx,q[i].ry);
            if(q[i].k<=cur){
                q1[++cnt1]=q[i];
            }else{
                q[i].k-=cur;
                q2[++cnt2]=q[i];
            }
        }
    }
    FOR(i,1,cnt1)
        if(!q1[i].id) T.upd(q1[i].lx,q1[i].ly,-1);
    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
int main(){
    CLOSE_TIE
    cin>>n>>Q;
    FOR(i,1,n) FOR(j,1,n) cin>>a[i][j], b[++bc]=a[i][j];
    sort(b+1,b+bc+1); bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n) FOR(j,1,n){
        a[i][j]=get(a[i][j]);
        q[++cnt]={i,j,i,j,a[i][j],0};
    }
    FOR(i,1,Q){
        Qu &c=q[++cnt];
        cin>>c.lx>>c.ly>>c.rx>>c.ry>>c.k;
        c.id=i;
    }
    solve(1,bc,1,cnt);
    FOR(i,1,Q) cout<<b[ans[i]]<<endl;
    return 0;
}

:::

类似离线二维数点，把矩形查询拆成两个行前缀查询。按行排序后扫描线，用一维树状数组维护。时间复杂度 O((n^2+q)\log^2 n)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=505;
const int QQ=6e4+5;
const int TOT=(QQ<<1)+N*N;
int n,Q,a[N][N],K[QQ],cnt,ans[QQ];
int b[N*N],bc;
struct Qu{int p,ly,ry,k,id;}q[TOT];
inline int get(int x){return lower_bound(b+1,b+bc+1,x)-b;}
struct BIT{
    #define lb (p&-p)
    int t[N];
    void upd(int p,int k){for(;p<=n;p+=lb) t[p]+=k;}
    int qry(int p){int res=0; for(;p;p-=lb) res+=t[p]; return res;}
    #undef lb
}T;
int sum[QQ];
Qu q1[TOT],q2[TOT];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr)
            if(q[i].id) ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    sort(q+ql,q+qr+1,[](Qu a,Qu b){return a.p==b.p?a.id<b.id:a.p<b.p;});
    FOR(i,ql,qr){
        if(!q[i].id){
            if(q[i].k<=mid){
                T.upd(q[i].ly,1);
                q1[++cnt1]=q[i];
            }else{
                q2[++cnt2]=q[i];
            }
        }else{
            sum[q[i].id]+=(T.qry(q[i].ry)-T.qry(q[i].ly-1))*q[i].k;
        }
    }
    FOR(i,ql,qr)
        if(q[i].id){
            int cur=sum[q[i].id];
            if(K[q[i].id]<=cur){
                q1[++cnt1]=q[i];
            }else{
                if(q[i].k==1) K[q[i].id]-=cur;
                q2[++cnt2]=q[i];
            }
        }
    FOR(i,ql,qr){
        if(!q[i].id&&q[i].k<=mid) T.upd(q[i].ly,-1);
        sum[q[i].id]=0;
    }
    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    CLOSE_TIE
    cin>>n>>Q;
    FOR(i,1,n) FOR(j,1,n) cin>>a[i][j], b[++bc]=a[i][j];
    sort(b+1,b+bc+1); bc=unique(b+1,b+bc+1)-b-1;
    FOR(i,1,n) FOR(j,1,n){
        a[i][j]=get(a[i][j]);
        q[++cnt]={i,j,j,a[i][j],0};
    }
    FOR(i,1,Q){
        int lx,rx,ly,ry; cin>>lx>>ly>>rx>>ry>>K[i];
        q[++cnt]={lx-1,ly,ry,-1,i};
        q[++cnt]={rx,ly,ry,1,i};
    }
    solve(1,bc,1,cnt);
    FOR(i,1,Q) cout<<b[ans[i]]<<endl;
    return 0;
}

:::

P3527 [POI 2011] MET-Meteors

把所有人捆到一起，对时间二分。对于时间段 [L,R]，执行在 [L,\frac{L+R}2] 内的所有操作，根据每个国家的太空站位置计算有哪些国家达到要求，哪些没有达到。

时间复杂度 O((m+k)\log k\log m)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=3e5+5;
int n,m,Q,ans[N];
ll a[N];
vector<int> pos[N];
struct Op{int l,r; ll k;}q[N];
struct BIT{
    #define lb (p&-p)
    ll t[N];
    void upd(int p,ll k){for(;p<=m;p+=lb) t[p]+=k;}
    void upd(int l,int r,ll k){
        upd(l,k), upd(r+1,-k);
    }
    ll qry(int p){
        ll res=0; for(;p;p-=lb) res+=t[p];
        return res;
    }
    #undef lb
}T;
int p[N],p1[N],p2[N];
inline void op(int i,int x){
    if(q[i].l<=q[i].r) T.upd(q[i].l,q[i].r,q[i].k*x);
    else{
        T.upd(q[i].l,m,q[i].k*x);
        T.upd(1,q[i].r,q[i].k*x);
    }
}
inline ll calc(int i){
    ll res=0;
    for(auto j:pos[i]){
        res+=T.qry(j);
        if(res>=a[i]) return res;
    }
    return res;
}
void solve(int l,int r,int ql,int qr){
    if(l>r||ql>qr) return;
    if(ql==qr){
        op(ql,1);
        FOR(i,l,r)
            if(calc(p[i])>=a[p[i]]) ans[p[i]]=ql;
        op(ql,-1);
        return;
    }
    int mid=(ql+qr)>>1,cnt1=0,cnt2=0;
    FOR(i,ql,mid) op(i,1);
    FOR(I,l,r){
        int i=p[I]; ll qwq=calc(i);
        if(qwq>=a[i]){
            p1[++cnt1]=i;
        }else{
            a[i]-=qwq;
            p2[++cnt2]=i;
        }
    }
    FOR(i,ql,mid) op(i,-1);
    FOR(i,1,cnt1) p[l+i-1]=p1[i];
    FOR(i,1,cnt2) p[l+cnt1+i-1]=p2[i];
    solve(l,l+cnt1-1,ql,mid);
    solve(l+cnt1,r,mid+1,qr);
}
int main(){
    CLOSE_TIE
    cin>>n>>m;
    FOR(i,1,m){
        int o; cin>>o;
        pos[o].psbk(i);
    }
    FOR(i,1,n) cin>>a[i];
    cin>>Q;
    FOR(i,1,Q) cin>>q[i].l>>q[i].r>>q[i].k;
    FOR(i,1,n) p[i]=i;
    solve(1,n,1,Q);
    FOR(i,1,n)
        if(ans[i]) cout<<ans[i]<<endl;
        else cout<<"NIE\n";
    return 0;
}

:::

P4597 序列 sequence

比较特殊的应用。对整个值域区间 [l,r] 进行二分，设当前考虑的序列区间为 [L,R]。对于当前值域中点 mid，计算分界线 p，使得将 [L, p] 赋值为 mid、[p+1, R] 赋值为 mid+1 时总代价最小。这个分界点将原问题划分为两个独立的子问题，然后递归处理左右两个值域区间即可。

时间复杂度：O(n\log V)（V 为值域）。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const int N=5e5+5;
const int inf=0x3f3f3f3f3f;
int n,a[N],ans[N];
void solve(int l,int r,ll vl,ll vr){
    if(l>r||vl>=vr) return;
    ll mid=(vl+vr)>>1,sum=0;
    FOR(i,l,r) sum+=abs(a[i]-mid-1);
    ll mins=sum,p=l-1;
    FOR(i,l,r){
        sum=sum-abs(a[i]-mid-1)+abs(a[i]-mid);
        if(sum<mins) mins=sum, p=i;
    }
    FOR(i,l,p) ans[i]=mid;
    FOR(i,p+1,r) ans[i]=mid+1;
    solve(l,p,vl,mid);
    solve(p+1,r,mid+1,vr);
}
int main(){
    CLOSE_TIE
    cin>>n;
    FOR(i,1,n) cin>>a[i];
    solve(1,n,-inf,inf);
    ll ANS=0;
    FOR(i,1,n) ANS+=abs(a[i]-ans[i]);
    cout<<ANS<<endl;
    return 0;
}

:::

P4331 [BalticOI 2004] Sequence (Day1)

上一题的单调递增版。z_i 单调递增等价于 \forall 1\le i<n, z_i\le z_{i+1}-1，两边同时减去 i 得到 z_i-i\le z_{i+1}-(i+1)。于是构造 \{z'_i=z_i-i\}，则 z_i 单调递增等价于 z'_i 单调不降，于是就转化为了上一题。然后我们要把答案变回来，对第 i 项 +i 即可。

P5163 WD与地图

时光倒流把删边转化为加边。一条边只有在其两端点在同一 SCC 时才是有效的，如果我们能预先知道每条边“在哪个时刻让两个 SCC 首次连通”，那么后续处理时，动态有向图的强连通维护就变成了静态按时间顺序的集合合并，直接用线段树合并就能处理。

考虑求出这个时刻。显然这个问题满足单调性，考虑整体二分。对于时间区间 [L,R]，将当前考虑的边中出现时间 \le mid 的加入临时图，跑 Tarjan 缩点（注意不要对孤立点跑，否则时间复杂度不对），对某条边会有以下情况：

如果边的两端属于同一 SCC。这说明其生效时间 \le mid，向左递归。
否则向右递归。这时我们对端点重标号到其所在 SCC 的代表点（任选），这可以看做一次缩点，代表我们已经考虑了出现时间 \le mid 的边。

之后处理询问就是常规操作了：对于每个时刻，把所有在此时刻生效的边全加进去，用动态开点的权值线段树维护每个连通块即可。

时间复杂度：O(q\log q+q\log V)，空间复杂度：O(q\log V)。

:::success[代码 & 评测记录]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
using ai3=array<int,3>;
#define FOR(i,a,b) for(int i=(a),EEE##i=(b); i<=EEE##i; i++)
#define REV(i,a,b) for(int i=(a),EEE##i=(b); i>=EEE##i; i--)
#define CLOSE_TIE ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define psbk emplace_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define fir first
#define sec second
const int N=1e5+5;
const int M=2e5+5;
const int V=1e9;
int n,m,Q,a[N],cnt;
int T[M];
pii ed[M];
map<pii,int> id;
struct Op{int op,a,b;}tmp[M];
struct Nd{int u,v,tim,id;}q[M<<1];

int dfn[N],low[N],dcnt,bel[N],bcnt,led[N];
bool ins[N];
stack<int> stk;
vector<int> e[N];
void dfs(int u){
    low[u]=dfn[u]=++dcnt;
    stk.push(u),ins[u]=1;
    for(int v:e[u]){
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        led[++bcnt]=u;
        while(1){
            int tp=stk.top(); stk.pop();
            bel[tp]=bcnt,ins[tp]=0;
            if(tp==u) break;
        }
    }
}

Nd q1[M<<1],q2[M<<1];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        FOR(i,ql,qr) T[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    vector<int> p;
    FOR(i,ql,qr){
        if(q[i].tim<=mid){
            auto [u,v,_,__]=q[i];
            e[u].psbk(v);
            p.psbk(u),p.psbk(v);
        }
    }
    for(int i:p)
        if(!dfn[i]) dfs(i);

    auto addq2=[&](int i){
        q[i].u=(bel[q[i].u]?led[bel[q[i].u]]:q[i].u);
        q[i].v=(bel[q[i].v]?led[bel[q[i].v]]:q[i].v);
        q2[++cnt2]=q[i];
    };
    FOR(i,ql,qr){
        if(q[i].tim<=mid){
            if(bel[q[i].u]==bel[q[i].v]&&bel[q[i].u]){
                q1[++cnt1]=q[i];
            }else addq2(i);
        }else addq2(i);
    }

    FOR(i,1,bcnt) led[i]=0;
    dcnt=bcnt=0; while(!stk.empty()) stk.pop();
    for(int i:p){
        dfn[i]=low[i]=bel[i]=ins[i]=0;
        e[i].clear();
    }

    FOR(i,1,cnt1) q[ql+i-1]=q1[i];
    FOR(i,1,cnt2) q[ql+cnt1+i-1]=q2[i];
    solve(l,mid,ql,ql+cnt1-1);
    solve(mid+1,r,ql+cnt1,qr);
}
bool del[M];

int f[N],rt[N];
int find(int p){return f[p]==p?p:f[p]=find(f[p]);}
struct SGT{
    #define mid ((l+r)>>1)
    int t[N*62],ls[N*62],rs[N*62],cnt;
    ll sum[N*62];
    inline void pushUp(int p){
        t[p]=t[ls[p]]+t[rs[p]];
        sum[p]=sum[ls[p]]+sum[rs[p]];
    }
    void upd(int &p,int l,int r,int x,int k){
        if(!p) p=++cnt;
        if(l==r){
            t[p]+=k;
            sum[p]=1ll*l*t[p];
            return;
        }
        if(x<=mid) upd(ls[p],l,mid,x,k);
        else upd(rs[p],mid+1,r,x,k);
        pushUp(p);
    }
    int merge(int p,int q,int l,int r){
        if(!p||!q) return p|q;
        if(l==r) return t[q]+=t[p],sum[q]+=sum[p],q;
        ls[q]=merge(ls[p],ls[q],l,mid);
        rs[q]=merge(rs[p],rs[q],mid+1,r);
        pushUp(q);
        return q;
    }
    ll qry(int p,int l,int r,int k){
        if(l==r) return 1ll*min(k,t[p])*l;
        int rtot=t[rs[p]]; ll rsum=sum[rs[p]];
        if(rtot>=k) return qry(rs[p],mid+1,r,k);
        else return rsum+qry(ls[p],l,mid,k-rtot);
    }
    #undef mid
}sgt;
inline void mrg(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    rt[fy]=sgt.merge(rt[fx],rt[fy],1,V);
    f[fx]=fy;
}
int ord[M];
int main(){
    CLOSE_TIE
    cin>>n>>m>>Q;
    FOR(i,1,n) cin>>a[i];
    FOR(i,1,m){
        int a,b; cin>>a>>b;
        ed[i]={a,b};
        id[{a,b}]=i;
    }
    FOR(i,1,Q){
        cin>>tmp[i].op>>tmp[i].a>>tmp[i].b;
        if(tmp[i].op==2){
            a[tmp[i].a]+=tmp[i].b;
            tmp[i].b*=-1;
        }
    }
    reverse(tmp+1,tmp+Q+1);
    FOR(i,1,Q){
        auto [op,a,b]=tmp[i];
        if(op==1){
            int ID=id[{a,b}];
            q[++cnt]={a,b,i,ID};
            del[ID]=1;
        }
    }
    FOR(i,1,m)
        if(!del[i]) q[++cnt]={ed[i].fir,ed[i].sec,0,i};
    solve(0,Q+1,1,cnt);

    vector<ll> ans;
    FOR(i,1,n) sgt.upd(rt[i],1,V,a[i],1), f[i]=i;
    FOR(i,1,m)
        if(T[i]==0) mrg(ed[i].fir,ed[i].sec);
    //要一次性把所有在 i 时刻生效的边全加进去，用 ord 存 T 升序排列后边的编号。
    FOR(i,1,m) ord[i]=i;
    sort(ord+1,ord+m+1,[](int x,int y){return T[x]<T[y];});
    int j=1;
    FOR(i,1,Q){
        auto [op,x,y]=tmp[i];
        for(; j<=m&&T[ord[j]]<=i; j++)
            if(T[ord[j]]==i) mrg(ed[ord[j]].fir,ed[ord[j]].sec);
        if(op==2){
            sgt.upd(rt[find(x)],1,V,a[x],-1);
            a[x]+=y;
            sgt.upd(rt[find(x)],1,V,a[x],1);
        }else if(op==3){
            ans.psbk(sgt.qry(rt[find(x)],1,V,y));
        }
    }
    reverse(all(ans));
    for(ll i:ans) cout<<i<<endl;
    return 0;
}

:::

参考资料

CDQ 分治 - OI Wiki
[笔记]CDQ 分治 - Sinktank
整体二分 - OI Wiki
P4597 序列sequence 题解 - water_tomato

本文已经过 deepseek 润色。