【cdq分治】
数据结构问题：
- 维护某种数据结构，使其对一系列操作（查询/修改）一次快速做出响应。
- “时间轴”：操作的顺序
如果需要实时进行响应，称为【在线算法】，在查询时立即回答，然后再继续进行下一次操作；否则需要预先知晓整个操作序列，经过一系列计算，批量回答所有查询，称为【离线算法】。
另外，根据两种操作在时间轴上分布的不同，可以再加以区分。边修改边查询，一般称为【动态问题】；不包含修改，或者所有查询都在修改之后，称为【静态问题】。
在一些离线的动态问题中，【cdq分治】提供了一种付出log(M)时间，将其转化成若干静态子问题的离线求解框架，其中M = 操作数量。有时也称cdq分治为【对于时间的分治算法】。
cdq分治的原理基于以下事实：
- 对于每个“查询”操作，其结果ans[i] = [1,i-1]中所有修改对其造成影响的叠加（这里的“叠加”需要能够比较方便的维护，例如sum/min/max等）
定义solve(l,r)为：对于第k个操作，k∈[l,r]，若其为查询操作，则计算[l,k-1]中的修改对ans[i]造成的影响。设 mid = (l+r)/2，solve(l,r)的执行步骤如下：
- 递归计算solve(l,mid);
- 计算[l,mid]中所有的修改对[mid+1,r]中所有查询所造成的影响;
- 递归计算solve(mid+1,r)
【P3810 【模板】三维偏序（陌上花开）】https://www.luogu.com.cn/problem/P3810
题意：有 n 个元素，第 i 个元素有 a[i]/b[i]/c[i] 三个属性，对于每个元素求 f[i] = “满足 a[j]<=a[i] && b[j]<=b[i] && c[j]<=c[i] 的 j 数量，j≠i”
众所周知，二维偏序问题的解决方法是树状数组（1个log）。三维偏序问题可以看成“动态”的二维偏序问题，b,c看成2维，a看成“时间轴”。
CDQ分治，第1维a（分治），第2维b（排序），第3维c（树状数组单点修改/前缀求和），复杂度2个log。注意先按a排序后将a赋值为rk[a]。
#pragma GCC optimize(3,"Ofast","inline")//O3优化 #pragma GCC optimize(2)//O2优化 #include <algorithm> #include <string> #include <cstring> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <iomanip> #include <ctime> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) const double eps = 1e-10; const int maxn = 2e5 + 10; const int mod = 10; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int n,k; int c[maxn],cnt[maxn]; struct node { int a,b,c,cnt,id,ans; }s1[maxn],s2[maxn]; bool cmpa(node n1,node n2) { if (n1.a == n2.a) { if (n1.b == n2.b) return n1.c < n2.c; else return n1.b < n2.b; } else return n1.a < n2.a; } bool cmpb(node n1,node n2) { if (n1.b == n2.b) return n1.c < n2.c; else return n1.b < n2.b; } int lowbit(int x) { return x & (-x); } void change(int x,int dx) { while (x <= k) { c[x] += dx; x += lowbit(x); } } int getsum(int x) { int s = 0; while (x) { s += c[x]; x -= lowbit(x); } return s; } void cdq(int l,int r) { if (l == r) return ; int mid = (l + r) / 2; cdq(l,mid); cdq(mid+1,r); sort(s2+l,s2+mid+1,cmpb); sort(s2+mid+1,s2+r+1,cmpb); int i,j = l; for (i = mid + 1;i <= r;i++) { while (s2[i].b >= s2[j].b && j <= mid) { change(s2[j].c,s2[j].cnt); j++; } s2[i].ans += getsum(s2[i].c); } for (i = l;i < j;i++) change(s2[i].c,-s2[i].cnt); } int main() { cin >> n >> k; for (int i = 1;i <= n;i++) { cin >> s1[i].a >> s1[i].b >> s1[i].c; } sort(s1+1,s1+1+n,cmpa); int v = 0; int cc = 0; for (int i = 1;i <= n;i++) { v++; if (s1[i].a != s1[i+1].a || s1[i].b != s1[i+1].b || s1[i].c != s1[i+1].c) { cc++; s2[cc].a = s1[i].a; s2[cc].b = s1[i].b; s2[cc].c = s1[i].c; s2[cc].cnt = v; s2[cc].id = cc; v = 0; } } cdq(1,cc); for (int i = 1;i <= cc;i++) { cnt[s2[i].ans+s2[i].cnt-1] += s2[i].cnt; } for (int i = 0;i < n;i++) cout << cnt[i] << endl; return 0; }
【P4093 [HEOI2016/TJOI2016]序列】https://www.luogu.com.cn/problem/P4093
设i这个位置的原值=a[i], 最小值=a0[i], 最大值=a1[i]
那么在j,i在选出子序列中相邻的条件是：
1. j<i
2. a[j]<=a0[i]
3. a1[j]<=a[i]三维偏序LIS，用CDQ分治+树状数组解决。可以修改1-询问1-修改2-询问2这样预排好；更好的方法是[l,mid]中的修改按a[j]排序，[mid+1,r]中的询问按a0[i]排序，双指针保证在询问i前进行了所有满足a[j]<=a0[i]的修改。
#pragma GCC optimize(3,"Ofast","inline")//O3优化 #pragma GCC optimize(2)//O2优化 #include <algorithm> #include <string> #include <cstring> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <iomanip> #include <ctime> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) const double eps = 1e-10; const int maxn = 2e5 + 10; const int mod = 10; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int n,m; int c[maxn],dp[maxn]; struct node { int v,l,r,id; }s[maxn]; bool cmpv(node n1,node n2) { return n1.v < n2.v; } bool cmpl(node n1,node n2) { return n1.l < n2.l; } bool cmpid(node n1,node n2) { return n1.id < n2.id; } int lowbit(int x) { return x & (-x); } void change(int x,int dx) { while (x <= n) { c[x] = max(c[x],dx); x += lowbit(x); } } void clear(int x) { while (x <= n) { c[x] = 0; x += lowbit(x); } } int getsum(int x) { int s = 0; while (x) { s = max(s,c[x]); x -= lowbit(x); } return s; } void cdq(int l,int r) { if (l == r) return ; int mid = (l + r) / 2; cdq(l,mid); sort(s+l,s+mid+1,cmpv); sort(s+mid+1,s+r+1,cmpl); int i,j = l; for (i = mid + 1;i <= r;i++) { while (j <= mid && s[j].v <= s[i].l) { change(s[j].r,dp[s[j].id]); j++; } dp[s[i].id] = max(dp[s[i].id],getsum(s[i].v)+1); } for (i = l;i < j;i++) clear(s[i].r); sort(s+mid+1,s+r+1,cmpid); cdq(mid+1,r); } int main() { cin >> n >> m; for (int i = 1;i <= n;i++) { cin >> s[i].v; s[i].l = s[i].v; s[i].r = s[i].v; s[i].id = i; } for (int i = 1;i <= m;i++) { int x,y; cin >> x >> y; s[x].l = min(s[x].l,y); s[x].r = max(s[x].r,y); } for (int i = 1;i <= n;i++) dp[i] = 1; cdq(1,n); int Max = 0; for (int i = 1;i <= n;i++) { Max = max(Max,dp[i]); } cout << Max << endl; return 0; }
【P4390 [BOI2007]Mokia 摩基亚】 https://www.luogu.com.cn/problem/P4390
题意：维护一个二维平面，动态支持单点加/矩阵求和。
众所周知，本题的静态版本（所有询问都在修改操作之后进行）可以使用 扫描线 + 树状数组 在1个log时间内解决。
直接套用cdq分治，第1维时间（分治），第2维x（排序），第3维y（树状数组单点修改/区间求和），复杂度2个log。
注意左边界的询问要--x，右边界的询问要在相同x的修改之后进行。
#pragma GCC optimize(3,"Ofast","inline")//O3优化 #pragma GCC optimize(2)//O2优化 #include <algorithm> #include <string> #include <cstring> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <iomanip> #include <ctime> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) const double eps = 1e-10; const int maxn = 2e6 + 10; const int mod = 10; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int n,cnt; int c[maxn]; struct node { int tim,x,y,v,id ,op; }s[maxn]; bool cmptim(node n1,node n2) { return n1.tim < n2.tim; } bool cmpx(node n1,node n2) { if (n1.x == n2.x) return n1.y < n2.y; else return n1.x < n2.x; } int lowbit(int x) { return x & (-x); } void change(int x,int dx) { while (x <= n) { c[x] += dx; x += lowbit(x); } } int getsum(int x) { int s = 0; while (x) { s += c[x]; x -= lowbit(x); } return s; } void cdq(int l,int r) { if (l == r) return ; int mid = (l + r) / 2; cdq(l,mid); cdq(mid+1,r); sort(s+l,s+mid+1,cmpx); sort(s+mid+1,s+r+1,cmpx); int i,j = l; for (i = mid + 1;i <= r;i++) { while (j <= mid && s[j].x <= s[i].x) { if (s[j].op == 0) change(s[j].y,s[j].v); j++; } if (s[i].op == 1) s[i].v += getsum(s[i].y); } for (i = l;i < j;i++) if (s[i].op == 0) change(s[i].y,-s[i].v); } int main() { int opt; cnt = 0; cin >> opt >> n; n++; cin >> opt; while (opt != 3) { if (opt == 1) { ++cnt; cin >> s[cnt].x >> s[cnt].y >> s[cnt].v; s[cnt].x += 1; s[cnt].y += 1; s[cnt].tim = cnt; s[cnt].id = cnt; s[cnt].op = 0; } else { int x,y,xx,yy; cin >> x >> y >> xx >> yy; xx++; yy++; ++cnt; s[cnt] = {cnt,x,y,0,cnt,1}; ++cnt; s[cnt] = {cnt,xx,yy,0,cnt,1}; ++cnt; s[cnt] = {cnt,x,yy,0,cnt,1}; ++cnt; s[cnt] = {cnt,xx,y,0,cnt,1}; } cin >> opt; } cdq(1,cnt); sort(s+1,s+1+cnt,cmptim); for (int i = 1;i <= cnt;i++) { if (s[i].op == 1) { cout << s[i].v + s[i+1].v - s[i+2].v - s[i+3].v << endl; i += 3; } } return 0; }
总结，CDQ分治解决的2个经典模型：
- 三位偏序，若某个问题能转化成三维偏序（例如二维LIS等），可以直接套CDQ分治；（要按照特定的顺序）
- 某个问题的动态版本，若其静态版本可以在O(len)时间内解决，可以套一个CDQ分治解决其动态版本，复杂度多付出一个logM （可以任意顺序）