【學習筆記】cdq 分治
一、定義
cdq 分治是一種離線分治算法，一般有三種用途：
-
處理點對之間的問題
-
優化 1D/1D 動態規劃
-
將動態問題轉為靜態問題
對于分治區間 \([l,r]\)，確定一個中點 \(mid\)，對于左右區間分別遞歸分治，然后再處理左右區間之間的貢獻。啊顯然歸并排序就是 cdq 分治。
二、例題
1.【模板】樹狀數組 1
將以此詢問拆成兩個單點的前綴和，而修改操作就是單點修改。考慮對于一個修改 \((x,y)\) 和詢問 \(p\)，如果修改發生在詢問前并且 \(x\le p\)，那么修改就會對詢問產生貢獻。對于操作序列中的分治區間 \([l,r]\)，我們按照類似歸并排序的方式去遍歷，那么左區間的修改操作就會影響到右區間的查詢操作。排序后的序列是按操作的位置升序的，于是我們再記錄一個 \(sum\) 表示當前增加了多少，對應地更新到答案中即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,m,ans[maxn];
struct node{
int typ,pos,val;
node(int typ=0,int pos=0,int val=0)
:typ(typ),pos(pos),val(val){}
il bool operator<(const node &x)const{
if(pos==x.pos){
return typ<x.typ;
}
else{
return pos<x.pos;
}
}
}a[maxn*3],b[maxn*3];
il void cdq(int l,int r){
if(l==r){
return ;
}
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
int p1=l,p2=mid+1,p3=l,sum=0;
for(int i=l;i<=r;i++){
if(p1<=mid&&a[p1]<a[p2]||p2>r){
if(a[p1].typ==1){
sum+=a[p1].val;
}
b[p3++]=a[p1++];
}
else{
if(a[p2].typ==2){
ans[a[p2].val]-=sum;
}
else if(a[p2].typ==3){
ans[a[p2].val]+=sum;
}
b[p3++]=a[p2++];
}
}
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
int cnt=0,tot=0;
for(int i=1,x;i<=n;i++){
cin>>x;
a[++cnt]=node(1,i,x);
}
while(m--){
int opt,x,y;
cin>>opt>>x>>y;
if(opt==1){
a[++cnt]=node(1,x,y);
}
else{
a[++cnt]=node(2,x-1,++tot);
a[++cnt]=node(3,y,tot);
}
}
cdq(1,cnt);
for(int i=1;i<=tot;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
2.[bzoj3262]陌上花開
三維偏序。第一維可以直接排序，第二維用 cdq 維護，第三維存入樹狀數組。這里不需要像歸并排序那樣寫，只需要按照 \(b\) 排序后，對于右區間的每個位置去找左區間有哪些滿足性質即可。注意去重。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,ans[maxn];
struct node{
int a,b,c,cnt,ans;
node(int a=0,int b=0,int c=0,int cnt=0,int ans=0)
:a(a),b(b),c(c),cnt(cnt),ans(ans){}
il bool operator<(const node &x)const{
if(a==x.a){
if(b==x.b){
return c<x.c;
}
return b<x.b;
}
return a<x.a;
}
}p[maxn],P[maxn];
il bool cmp(const node &x,const node &y){
if(x.b==y.b){
return x.c<y.c;
}
return x.b<y.b;
}
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=m;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
il void cdq(int l,int r){
if(l==r){
return ;
}
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
sort(P+l,P+mid+1,cmp);
sort(P+mid+1,P+r+1,cmp);
int pp=l;
for(int i=mid+1;i<=r;i++){
while(pp<=mid&&P[i].b>=P[pp].b){
add(P[pp].c,P[pp].cnt);
pp++;
}
P[i].ans+=query(P[i].c);
}
for(int i=l;i<pp;i++){
add(P[i].c,-P[i].cnt);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,a,b,c;i<=n;i++){
cin>>a>>b>>c;
p[i]=node(a,b,c);
}
sort(p+1,p+n+1);
int tot=0;
for(int i=1,num=0;i<=n;i++){
num++;
if(p[i].a!=p[i+1].a||p[i].b!=p[i+1].b||p[i].c!=p[i+1].c){
P[++tot]=node(p[i].a,p[i].b,p[i].c,num);
num=0;
}
}
cdq(1,tot);
for(int i=1;i<=tot;i++){
ans[P[i].cnt+P[i].ans-1]+=P[i].cnt;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
3.[bzoj1176][Balkan2007]Mokia
類似例 1，將查詢差分后并入操作序列中。那么時間是一維，橫豎各是一維，一共就有三維。那么就需要 cdq 套樹狀數組了。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1.6e5+5,maxm=2e6+5;
int n,m,ans[maxn];
struct node{
int typ,xp,yp,val;
node(int typ=0,int xp=0,int yp=0,int val=0)
:typ(typ),xp(xp),yp(yp),val(val){}
il bool operator<(const node &x)const{
if(xp==x.xp){
return typ<x.typ;
}
return xp<x.xp;
}
}a[maxn<<2],b[maxn<<2];
int tr[maxm];
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
il void cdq(int l,int r){
if(l==r){
return ;
}
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
int p1=l,p2=mid+1,p3=l;
for(int i=l;i<=r;i++){
if(p1<=mid&&a[p1]<a[p2]||p2>r){
if(a[p1].typ==1){
add(a[p1].yp,a[p1].val);
}
b[p3++]=a[p1++];
}
else{
if(a[p2].typ==2){
ans[a[p2].val]+=query(a[p2].yp);
}
else if(a[p2].typ==3){
ans[a[p2].val]-=query(a[p2].yp);
}
b[p3++]=a[p2++];
}
}
for(int i=l;i<=mid;i++){
if(a[i].typ==1){
add(a[i].yp,-a[i].val);
}
}
// for(int i=0;i<=n;i++){
// cout<<query(i)<<" ";
// }
// puts("");
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>m>>n;
int opt,tot=0,cnt=0;
while(cin>>opt){
if(opt==1){
int x,y,v;
cin>>x>>y>>v;
a[++tot]=node(1,x,y,v);
}
else if(opt==2){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
ans[++cnt]=m*(x2-x1+1)*(y2-y1+1);
a[++tot]=node(2,x1-1,y1-1,cnt);
a[++tot]=node(2,x2,y2,cnt);
a[++tot]=node(3,x1-1,y2,cnt);
a[++tot]=node(3,x2,y1-1,cnt);
}
}
cdq(1,tot);
for(int i=1;i<=cnt;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
4.[Violet 3]天使玩偶
兩點 \((x_i,y_i),(x_j,y_j)\) 間的距離為 \(|x_i-x_j|+|y_i-y_j|\)，當 \(x_i\ge x_j\land y_i\ge y_j\) 時，就變成了 \((x_i+y_i)-(x_j+y_j)\)。于是我們可以對左上，左下，右上，右下各跑一遍 cdq 套樹狀數組。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,lim=1e6+1;
int n,m,tot,cnt,ans[maxn];
struct node{
int typ,xx,yy;
node(int typ=0,int xx=0,int yy=0)
:typ(typ),xx(xx),yy(yy){}
il bool operator<(const node &x)const{
if(xx==x.xx){
return typ<x.typ;
}
return xx<x.xx;
}
}hp[maxn],a[maxn],b[maxn];
struct{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void init(){
memset(tr,-0x3f,sizeof tr);
}
il void upd(int p,int x){
for(;p<=lim;p+=lowbit(p)){
tr[p]=max(tr[p],x);
}
}
il int query(int p){
int res=-1e9;
for(;p;p-=lowbit(p)){
res=max(res,tr[p]);
}
return res;
}
il void clear(int p){
for(;p<=lim;p+=lowbit(p)){
tr[p]=-1e9;
}
}
}F;
il void cdq(int l,int r){
if(l==r){
return ;
}
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
int p1=l,p2=mid+1,p3=l;
for(int i=l;i<=r;i++){
if(p1<=mid&&a[p1]<a[p2]||p2>r){
if(!a[p1].typ){
F.upd(a[p1].yy,a[p1].xx+a[p1].yy);
}
b[p3++]=a[p1++];
}
else{
if(a[p2].typ){
ans[a[p2].typ]=min(ans[a[p2].typ],a[p2].xx+a[p2].yy-F.query(a[p2].yy));
}
b[p3++]=a[p2++];
}
}
for(int i=l;i<=mid;i++){
if(!a[i].typ){
F.clear(a[i].yy);
}
}
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
il void work(bool flax,bool flay){
for(int i=1;i<=tot;i++){
a[i].typ=hp[i].typ;
if(flax){
a[i].xx=hp[i].xx;
}
else{
a[i].xx=lim-hp[i].xx+1;
}
if(flay){
a[i].yy=hp[i].yy;
}
else{
a[i].yy=lim-hp[i].yy+1;
}
}
cdq(1,tot);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,x,y;i<=n;i++){
cin>>x>>y;
hp[++tot]=node(0,x+1,y+1);
}
while(m--){
int opt,x,y;
cin>>opt>>x>>y;
if(opt==1){
hp[++tot]=node(0,x+1,y+1);
}
else{
hp[++tot]=node(++cnt,x+1,y+1);
}
}
memset(ans,0x3f,sizeof ans);
F.init();
work(0,0),work(0,1),work(1,0),work(1,1);
for(int i=1;i<=cnt;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
5.[Cqoi2011]動態逆序對
考慮對答案進行差分，求出每一次刪除到下一次刪除的逆序對減少數，再做后綴和。
對于兩個元素 \(i\) 和 \(j\)，如果它們的值為 \(val\)，下標為 \(pos\)，被刪除的時間為 \(time\)，那么如果滿足 \((val_i<val_j\land pos_i>pos_j)\lor(val_i>val_j\land pos_i<pos_j)\)，就可以產生一個逆序對。欽定 \(time_i<time_j\)，這就對 \(time_i\) 的答案產生了 \(1\) 的貢獻。這是一個三維偏序問題，cdq 即可。
值得注意的是 \(m\) 次操作不一定會把數組刪完，而對于最后剩下的那部分元素在 cdq 里是不容易直接計算的（因為 \(time\) 相同）。所以對于剩下的那部分不妨直接用樹狀數組處理掉。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,ans[maxn];
struct node{
int tim,pos,val;
}a[maxn],b[maxn];
struct{
int n,tr[maxn];
il void init(){
memset(tr,0,sizeof tr);
}
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=1e5;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
}F;
template<typename T>il void cdq(int l,int r,T cmp){
if(l==r){
return ;
}
int mid=(l+r)>>1;
cdq(l,mid,cmp),cdq(mid+1,r,cmp);
int p1=l,p2=mid+1,p3=l;
for(int i=l;i<=r;i++){
if(p1<=mid&&cmp(a[p1],a[p2])||p2>r){
F.add(a[p1].tim,1);
b[p3++]=a[p1++];
}
else{
ans[a[p2].tim]+=F.query(1e5)-F.query(a[p2].tim);
b[p3++]=a[p2++];
}
}
for(int i=l;i<=mid;i++){
F.add(a[i].tim,-1);
}
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,x;i<=n;i++){
cin>>x;
a[x].val=x,a[x].pos=i;
}
for(int i=1,x;i<=m;i++){
cin>>x;
a[x].tim=i;
}
for(int i=1;i<=n;i++){
if(!a[i].tim){
a[i].tim=m+1;
ans[m+1]+=F.query(1e5)-F.query(a[i].pos);
F.add(a[i].pos,1);
}
}
F.init();
sort(a+1,a+n+1,[](const node &x,const node &y){return x.pos<y.pos;});
cdq(1,n,[](const node &x,const node &y){return x.val>y.val;});
sort(a+1,a+n+1,[](const node &x,const node &y){return x.pos>y.pos;});
cdq(1,n,[](const node &x,const node &y){return x.val<y.val;});
for(int i=m;i;i--){
ans[i]+=ans[i+1];
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
6.[Tjoi2016&Heoi2016]序列
記每個位置 \(i\) 可能變成的值（不包括原數組）中最大的為 \(mx_i\)，最小的為 \(mn_i\)，設 \(dp_i\) 表示以 \(i\) 結尾的最長合法子序列的長度，那么有轉移方程：
\[dp_i=\max_{j<i\land a_j\le a_i\land mx_j\le a_i\land a_j\le mn_i}\{dp_j+1\}
\]
看起來是個四維偏序，不是很好優化（總不能 cdq 套樹套樹吧？）。考慮將 \(mx_i\) 和 \(mn_i\) 分別與 \(a_i\) 取最大、最小值，那么第二個條件就可以省掉了。也就是說只需滿足三維偏序：
\[\begin{cases}
j<i\\
mx_j\le a_i\\
a_j\le mn_i
\end{cases}
\]
那么就可以用 cdq 優化了。每次都需要將自己和左右區間重新排序。注意由于 dp 的轉移順序是固定的，因此一定要先遞歸左區間，再處理左右區間之間的轉移，再遞歸右區間。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,dp[maxn];
struct node{
int val,mx,mn,pos;
}a[maxn];
struct fenwick{
int tr[maxn];
fenwick(){
memset(tr,-0x3f,sizeof tr);
}
il int lowbit(int x){
return x&-x;
}
il void upd(int p,int v){
for(;p<=1e5;p+=lowbit(p)){
tr[p]=max(tr[p],v);
}
}
il void clear(int p){
for(;p<=1e5;p+=lowbit(p)){
tr[p]=-1e9;
}
}
il int query(int p){
int res=-1e9;
for(;p;p-=lowbit(p)){
res=max(res,tr[p]);
}
return res;
}
}F;
il void cdq(int l,int r){
sort(a+l,a+r+1,[](const node &x,const node &y){return x.pos<y.pos;});
if(l==r){
// cout<<a[l].pos<<" "<<dp[a[l].pos]<<"\n";
dp[a[l].pos]=max(dp[a[l].pos],1);
return ;
}
int mid=(l+r)>>1;
cdq(l,mid);
sort(a+l,a+mid+1,[](const node &x,const node &y){return x.mx<y.mx;});
sort(a+mid+1,a+r+1,[](const node &x,const node &y){return x.val<y.val;});
int p1=l,p2=mid+1;
for(int i=l;i<=r;i++){
if(p1<=mid&&a[p1].mx<=a[p2].val||p2>r){
F.upd(a[p1].val,dp[a[p1].pos]);
p1++;
}
else{
dp[a[p2].pos]=max(dp[a[p2].pos],F.query(a[p2].mn)+1);
p2++;
}
}
for(int i=l;i<=mid;i++){
F.clear(a[i].val);
}
cdq(mid+1,r);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].mx=a[i].mn=a[i].val;
a[i].pos=i;
}
for(int i=1,p,v;i<=m;i++){
cin>>p>>v;
a[p].mx=max(a[p].mx,v);
a[p].mn=min(a[p].mn,v);
}
cdq(1,n);
int ans=0;
for(int i=1;i<=n;i++){
// cout<<dp[i]<<" ";
ans=max(ans,dp[i]);
}
// cout<<"\n";
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號