#创作计划#整体二分与CDQ分治（二）

Xylophone

2025-12-14 17:19:34

发布于：广东

32阅读

0回复

0点赞

上一期

中场休息

我们来讲讲一些整体二分的细节。

1.答案的归属。设当前 $mid$ 检查出来的值 $t$ 等于所询问的 $k$ 值，此时这个询问是应当分到左组还是分到右组呢？
答：左组。左组答案区间为 $[l,mid]$ ，右组答案区间为 $(mid,r]$ ,如果答案刚好为 $mid$ 分到左组才能得到正确答案。
2.整体二分的小优化
注意到当操作集合中不包含询问操作时，该集合无效。因此可以判断左组和右组是否有询问，有再进行递归。使用这个技巧的代码将在 P4602 给出。
以下是一些使用该技巧的测试结果。

所用时长(最长/总数）	P4137	P1527	P3332	P4602
普通写法	$197ms/2.08s$	$247ms/2.77s$	$273ms/1.8s$	$176ms/1.65s$
优化写法	$149ms/1.57s$	$243ms/2.73s$	$269ms/1.69s$	$164ms/1.54s$

可以看出这个优化还是有一定用处的。
这个优化对于大部分整体二分来说最多优化 $O(NlogN)$ ,因为它优化的是插入操作，一般的整体二分中插入会进行 N 次，复杂度为 $O(NlogN)$ ，为该优化的上限。
P4602为特殊情况，见后文。

第二部分 $CDQ$ 分治

本篇仅讲述 $CDQ$ 分治用于处理点对的应用，更多应用详见 OI-wiki
老规矩，if 你看完全篇还不会，考虑此视频
$CDQ$ 分治的经典应用是三维偏序。
先考虑二维偏序，有两种解法：
1.归并排序求解。归并时先被分进主序列的左组元素都对右组该元素的逆序对产生贡献。可以上网寻找资料。
2.树状数组（线段树）求解。由于二维偏序通常是给定若干元素，按元素位置进行贡献，因此无须去重。按位置从左到右依个将元素值加入树状数组，在加入一个元素前先计算它的值~最大值的下标的和，即为在它之前又比它大的元素数量；也可倒序插入，插入前计算1~该元素的值。
$CDQ$ 分治求解的前置知识是第二种二位偏序解法。

题目描述

有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 且 $j\ne i$ 的 $j$ 的数量。

对于所有 $d \in [0, n)$ ，求 $f(i)=d$ 的数量。

~~ K-D 树和二维树状数组套值域树状数组一眼题~~
设三个属性分别为 $a$ , $b$ 和 $c$
$CDQ$ 分治的做法是将数组分为两组，确保左组无法从右组获得贡献，右组可以从左组获得贡献。将这个性质定义为性质 A，体现为左组的某个属性小于等于右组的该属性。
先将所有元素按 $a$ 从小到大排序，这样无论如何分组左边元素的 $a$ 一定比右边的元素的 $a$ 小，确保符合性质 A。然后进行分治： $CDQ$ 分治是正常写法，先求解子问题再求解当前主问题，因此先分治；在每次递归结尾将 $[l,r]$ 元素的 $b$ 从小到大进行排序，由于已对 $a$ 进行了排序，所以无论对该区间的元素怎样重排，**不难注意到它左边的所有元素的 $a$ 都小于它的任意一个元素的 $a$ ；它右边所有元素的 $a$ 都大于它任意元素的 $a$ **.处理 $[l,r]$ 时，可得 $[l,mid]$ 中的所有 $a\leq[mid+1,r]$ 中的所有 $a$ , 并且这两个子区间内的 $b$ 保持有序。
接下来采用双指针的做法，如果左组当前元素的 $b$ 小于右组当前元素的 $b$ ，那么将右组指针后移，寻找更大的 $b$ ; 当目前右组元素的 $b$ 大于左组当前元素的 $b$ 时，持续将左组指针后移并将左组元素的 $c$ 值插入树状数组直到 $b$ 小于左组当前元素的 $b$ .注意到此时左组当前元素的前驱和右组当前元素的 $a$ 和 $b$ 都符合性质 A，由于左组在之前（即当前元素前驱的左边）的元素 $a$ 依旧比右组的 $a$ 小，并且它们的 $b$ 经过排序，一定比左组当前元素的 $b$ 小。可以得出左组第一个到当前元素前驱的所有元素 $a$ 和 $b$ 都符合性质 A,使用树状数组的方式将左组所有 $c$ 符合性质A的元素统计答案（这时所有 $a、b$ 小于该元素的元素都将 $c$ 值插入，这时统计1~该元素 $c$ 值可以得到三者都比其小的左组所有元素数）。左右指针都推完后结束该区间计算，记得将所有元素按照 $b$ 排序。请对照代码理解。
注意：以上思路其实有错误。你能找出来吗（朵拉音）
~~BYD ACGO 的 Markdown 为什么不兼容 HTML~~
错误：当 $a$ 相等时， $b$ 和 $c$ 处于乱序，有可能将较小的 $b、c$ 值分到较大的元素的右边，导致它们无法被这些较大的元素统计。学过超难超简单的结构体排序的你想到可以在 $a$ 相同时按 $b$ 排，然后 $b$ 相同随便乱排（或者直接不排，会默认左参数小于右参数），这样你就能 AC 啦。

AC 记录：

没有。

哪里 AC 了，什么地方满足性质 A 了，你把三个属性都相同的元素当成什么了？
注意可以把三个属性相同的元素并成一个，树状数组插入时不加1而是加上这个元素的大小（就是共有多少元素相等然后并成这个元素），统计完将所有元素的答案加上大小再减去一（因为与其相等的所有其它元素都有贡献）即可。
$Code:$

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c,id;
    bool operator <(const node&xyl)const{
        if(a!=xyl.a)return a<xyl.a;
        if(b!=xyl.b)return b<xyl.b;
        return c<xyl.c;
    }
}tmp[100005],a[100005],k[100005];
int n,N,m,sz[100005],ans[100005],cnt[100005],tree[200005],idx[100005],res[100005];
void modify(int x,int d){
    for(int i=x;i<=m;i+=i&(-i))tree[i]+=d;
}
int sum(int x){
    int res=0;
    for(int i=x;i>=1;i-=i&(-i))res+=tree[i];
    return res;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1,i=l;
    cdq(l,mid),cdq(mid+1,r);
    while(cnt1<=mid&&cnt2<=r){
        if(a[cnt1].b<=a[cnt2].b)modify(a[cnt1].c,sz[a[cnt1].id]),k[i++]=a[cnt1++];
        else ans[a[cnt2].id]+=sum(a[cnt2].c),k[i++]=a[cnt2++];
    }
    while(cnt1<=mid)modify(a[cnt1].c,sz[a[cnt1].id]),k[i++]=a[cnt1++];
    while(cnt2<=r)ans[a[cnt2].id]+=sum(a[cnt2].c),k[i++]=a[cnt2++];
    for(int i=l;i<=mid;++i)modify(a[i].c,-sz[a[i].id]);
    for(int i=l;i<=r;++i)a[i]=k[i];
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)tmp[i]={read(),read(),read(),0};
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;++i){
        if(tmp[i].a!=tmp[i-1].a||tmp[i].b!=tmp[i-1].b||tmp[i].c!=tmp[i-1].c)a[++N]=tmp[i],a[N].id=N;
        sz[N]++,idx[i]=N;
    }
    cdq(1,N);
    for(int i=1;i<=n;++i)res[ans[idx[i]]+sz[idx[i]]-1]++;
    for(int i=0;i<n;++i)write(res[i]),putchar('\n');
    return 0;
}

AC 是 AC 了，排序在哪呢？
没错，双指针时顺手进行归并排序了
~~当然后面你就会见到我 sort 的写法因为归并有点不省事~~
依旧分享本题写法：
$CDQ$ 分治， $O(NlogNlogV)$ (离散化 $O(Nlog^2N)$ )；
整体二分（是的，居然是整体二分） $O(NlogNlogV)$ (离散化 $O(Nlog^2N)$ )；
树套树 $O(NlogN)$ ；
$K-D$ 树 $O(N\sqrt N)$ ；
分块 $O(N\sqrt N)$ ；
莫队 $O(N\sqrt N)$
二进制分组套小波矩阵 $O((N+M)log^2N)$
bitset, $O(\frac{N^2}{w})$
注意！ $CDQ$ 分治的重要细节！虽然可能没人错，但是在所有右组遍历完后还是要把左组操作进行，因为后面清空 BIT（ST）要全部抵消

接下来回到上一期开头的问题：动态逆序对
请自行读题。
~~读题之后容易发现最后一个输入没用~~
可以发现每次输出的答案后一个都比前一个小
看似是废话，那我们思考一下小了多少呢？
很明显是删除元素对答案的负贡献。每个答案都多计算一个元素的负贡献，可以考虑用类似前缀和的方法。先计算原序列总贡献，再递推每个删除元素的负贡献。
问题转化为：如何寻找负贡献？
先对代码进行简化，不需要去重，并考虑用sort直接实现。接下来可以将元素被删时间 $Time$ 看作第三维的属性，注意到对于删除操作 $i$ ,其负贡献的倒数为序列中满足 $Time_i < Time_j,$ $Val_i<Val_j,$ $Pos_i>Pos_j$ 或 $Time_i<Time_j,$ $Val_i>Val_j,$ $Pos_i<Pos_j$ 的元素个数。将其转化为三维偏序问题，进行答案运算时不考虑 $Time$ ,将序列从左到右遍历统计第一种贡献，再倒序处理第二种贡献。删除时像整体二分，用-1抵消插入操作；在计算贡献时乘上自己的 op ，确保插入操作统计正贡献、删除操作统计负贡献。本题有一定思考难度，请自行理解。
注意到求的是逆序对数量的总和，再看看数据量，不开 long long 见祖宗
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int pos,val,op,id;
    bool operator <(const node&xyl)const{return pos<xyl.pos;}
}a[150005];
int n,N,m,ans[50005],tree[100005],idx[100005];
void modify(int x,int d){
    for(int i=x;i<=n;i+=i&(-i))tree[i]+=d;
}
int sum(int x){
    int res=0;
    for(int i=x;i>=1;i-=i&(-i))res+=tree[i];
    return res;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq(l,mid),cdq(mid+1,r);
    for(;cnt2<=r;++cnt2){
        while(cnt1<=mid&&a[cnt1].pos<a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),++cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*(sum(n)-sum(a[cnt2].val));
    }
    for(int i=l;i<cnt1;++i)modify(a[i].val,-a[i].op);
    for(cnt1=mid,cnt2=r;cnt2>=mid+1;--cnt2){
        while(cnt1>=l&&a[cnt1].pos>a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),--cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*sum(a[cnt2].val-1);
    }
    for(int i=mid;i>cnt1;--i)modify(a[i].val,-a[i].op);
    sort(a+l,a+r+1);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[++N]={i,read(),1,0},idx[a[N].val]=i;
    for(int i=1;i<=m;++i)a[++N].val=read(),a[N].pos=idx[a[N].val],a[N].id=i,a[N].op=-1;
    cdq(1,N);
    for(int i=1;i<m;++i)ans[i]+=ans[i-1];
    for(int i=0;i<m;++i)write(ans[i]),putchar('\n');
    return 0;
}

所有解法：
$CDQ$ 分治 $O(Nlog^2N)$
树状数组套主席树 $O(Nlog^2N)$
分块 $O(N\sqrt N)$
线段树套平衡树 $O(NlogN+Mlog^2N)$ （甚至题解还有线段树套朴素BST）
$K-D$ 树 $O(N\sqrt N)$

第三部分（部分）拓展问题

来点饮料怎么样？
毒瘤例题1：经典牢题 P4602 [CTSC2018] 混合果汁
也是做出 CTSC 了（虽然难度是紫）
自行观看题面！
本贴将会讲解两种解法。

没错，主席树

前排提醒：这只是主席树的一种做法
步骤：
1.一眼二分法。比答案小的所有美味度都能符合要求，比答案大的美味度不能，符合单调性。
2.考虑进行一次询问。每次 check 应尽量取美味度大于 $mid$ 、单价最小的果汁，取完体积再判断价格是否符合标准。可以建立值域线段树，以单价为下标，维护区间体积和与区间花费和（将区间所有果汁买下的花费），在值域线段树上进行线段树二分，可用体积小于等于左子树则向左递归，大于则更新可用体积并向右递归，最后返回消费和。如何维护美味值大于等于 $mid$ 的约束条件？注意到每次只有美味值在区间 $[mid,maxn]$ 的元素可用，形成一个后缀关系。将美味值从大到小排列，将后缀关系转化为前缀关系，只考虑前缀的所有元素，明显可用主席树维护。具体编码时先从大到小排序美味度，然后建立主席树，二分某种果汁之前的所有果汁是否可用（而不用对美味度值域建树），再按上述步骤二分。注意到每次 check 复杂度为 $O(logN)$ ,一次二分答案为 $O(log^2N)$ .推广到多次询问，~~可以用整体二分~~直接在线对每一个询问回答即可。总复杂度 $O(Nlog^2N)$ 。
~~哪有人两步推出解法的~~
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int d,p,l;
    bool operator <(const node&xyl)const{return d>xyl.d;}
}a[100005];
int n,q,cnt,root[100005],g,L;
struct pst{
    int l,r,cost,vol;
}t[100005<<5];
void add(int &cur,int lst,int l,int r,int p,int v){
    cur=++cnt;
    t[cur]=t[lst];
    t[cur].cost+=p*v,t[cur].vol+=v;
    if(l==p&&r==p)return;
    int mid=l+r>>1;
    if(p<=mid)add(t[cur].l,t[lst].l,l,mid,p,v);
    else add(t[cur].r,t[lst].r,mid+1,r,p,v);
}
int query(int cur,int l,int r,int p){
    if(l==r)return l*p;
    if(t[t[cur].l].vol>=p)return query(t[cur].l,l,l+r>>1,p);
    else return t[t[cur].l].cost+query(t[cur].r,(l+r>>1)+1,r,p-t[t[cur].l].vol);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;++i)a[i]={read(),read(),read()};
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)add(root[i],root[i-1],1,100005,a[i].p,a[i].l);
    while(q--){
        g=read(),L=read();
        int l=1,r=n,ans=-1,mid,k;
        while(l<=r){
            mid=l+r>>1,k=query(root[mid],1,100005,L);
            if(k<=g&&t[root[mid]].vol>=L)ans=mid,r=mid-1;
            else l=mid+1;
        }
        write(~ans?a[ans].d:ans),putchar('\n');
    }
    return 0;
}

没错，整体二分

注意你谷有很多复杂度假的整体二分，也就是 $O(Nlog^3N)$ 甚至 $O(N^2log^2N)$ ,请以我学习的这种思路和代码为参考，或者自己证明自己做法的复杂度。
貌似可以一次二分中再二分符合要求的价格，但是这样就会是二分套二分套整体二分，复杂度为 $O(Nlog^3N)$ .
1.与上述一样。
2.用整体二分套值域线段树。利用值域线段树二分，判断询问分到哪组。区别是不像主席树开~~一瞬千树~~一堆线段树，而是一次性使用，用的时候插元素进去，用完清空。但是如果每次都从 $mid$ 的果汁插到 $r$ 的果汁复杂度会假，因此每次都复用原来的权值线段树，往左就插入更多元素，往右就删掉一些元素。如何证明复杂度？
注意到整体二分使用了递归，本质上是从值域的左到右执行操作，而不是同时进行，可以依此证明。
插入的用时分为从该轮递归跳到同一层递归和从该轮递归跳到更高层的递归。每层插入复杂度为左右层相加再加上左层最底部跳到右层最顶部的复杂度。计算得如下式：
$t(N)=2t(N/2)+3N/4$
计算次数为 $O(NlogN)$ ,每次插入 $O(logN)$ ,故总插入复杂度为 $O(Nlog^2N)$ ,高于一般整体二分的 $O(NlogN)$ ,但是加上询问为 $O((N+Q)log^2N)$ ,依旧达标。使用小技巧优化只能优化少数极端情况或递归开销。
整体二分可能比主席树更难理解，但是……
$Code!$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
int n,m,vol[N<<2],cost[N<<2],cur,ans[N];
struct node{
	int d,p,l;
	bool operator <(const node&x){return d>x.d;}
}a[N];
struct xyl{
	int g,l,id;
}q[N],q1[N],q2[N];
void pushup(int p){vol[p]=vol[p<<1]+vol[p<<1|1],cost[p]=cost[p<<1]+cost[p<<1|1];}
void add(int p,int l,int r,int P,int L){
	if(l==r){
		vol[p]+=L;
		cost[p]=vol[p]*l;
		return;
	}
	int mid=l+r>>1;
	if(P<=mid)add(p<<1,l,mid,P,L);
	else add(p<<1|1,mid+1,r,P,L);
	pushup(p);
}
int query(int p,int l,int r,int v){
	if(!v)return 0;
	if(l==r)return l*v;
	int mid=l+r>>1;
	if(vol[p<<1]>=v)return query(p<<1,l,mid,v);
	else return cost[p<<1]+query(p<<1|1,mid+1,r,v-vol[p<<1]);
}
void solve(int l,int r,int ql,int qr){
	if(ql>qr)return;
	if(l==r){
		for(int i=ql;i<=qr;++i)ans[q[i].id]=a[l].d;
		return;
	}
	int mid=l+r>>1,cnt1=0,cnt2=0;bool b1=0,b2=0;
	while(cur<mid)++cur,add(1,1,N,a[cur].p,a[cur].l);
	while(cur>mid)add(1,1,N,a[cur].p,-a[cur].l),--cur;
	for(int i=ql;i<=qr;++i){
		if(vol[1]>=q[i].l&&query(1,1,N,q[i].l)<=q[i].g)q1[++cnt1]=q[i],b1=1;
		else q2[++cnt2]=q[i],b2=1;
	}
	for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
	for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
	if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]={read(),read(),read()};
	a[++n]={-1,0,N};
	sort(a+1,a+n+1);
	for(int i=1;i<=m;++i)q[i]={read(),read(),i};
	solve(1,n,1,m);
	for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
	return 0;
}

时间复杂度： $O(NlogNlogV)$
本题其它解法：树状数组套树状数组 $O(Nlog^3N)$ （解法最少的一集）

这期就到此为止了。也许有机会我还会把第三部分的例题补完。Say↑goodbye~

有帮助，赞一个

去预览

0/2000

全部评论 7

༺ཌༀཉི༒白·羊༒༃ༀད༻
看了辣么久，终于看完了

4天前来自上海
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  ~~但是后半部分没看懂~~
  
  4天前来自上海
  0
- Xylophone
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  QvQ 蟹蟹，有人认真看我的帖子耶
  
  4天前来自广东
  0
- Xylophone
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  那个后半，CDQ的后半还是混合果汁那里
  
  4天前来自广东
  0
priority（不加团队）
我觉得可以把第一篇的链接挂上

1周前来自浙江
1
- Xylophone
  回复priority（不加团队）
  允
  
  1周前来自广东
  0
- priority（不加团队）
  回复Xylophone
  再把第二篇的链接挂第一篇上
  
  1周前来自浙江
  0
- priority（不加团队）
  回复Xylophone
  个人觉得很方便（
  
  1周前来自浙江
  0
priority（不加团队）
帮顶

1周前来自浙江
1
- Xylophone
  回复priority（不加团队）
  蟹蟹
  
  1周前来自广东
  0
Xylophone
我的收视率怎么样了

1周前来自广东
1
Xylophone
https://www.acgo.cn/person/36482
我真求你了，我什么都会做的，外文空格我会打的，句号我也会加的，主人

4天前来自广东
0
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

4天前来自上海
0
༺ཌༀཉི༒白·羊༒༃ༀད༻
qpzc

5天前来自上海
0
- Xylophone
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  蟹蟹
  
  5天前来自广东
  0