CDQ分治小结
程序员文章站
2022-07-02 17:34:20
CDQ分治小结 warning:此文仅用博主复习使用,初学者看的话后果自负。。 复习的时候才发现以前根本就没写过这种东西的总结,简单的扯一扯 cdq分治的经典应用就是解决偏序问题 比如最经典的三维偏序问题 给出$n$个数,每个数$i$,有三个属性$a_i, b_i, c_i$,现在我们要统计对于每个 ......
cdq分治小结
warning:此文仅用博主复习使用,初学者看的话后果自负。。
复习的时候才发现以前根本就没写过这种东西的总结,简单的扯一扯
cdq分治的经典应用就是解决偏序问题
比如最经典的三维偏序问题
给出\(n\)个数,每个数\(i\),有三个属性\(a_i, b_i, c_i\),现在我们要统计对于每个\(i\),\(a_j \leqslant a_i, b_j \leqslant b_i, c_j \leqslant c_i\)的个数
显然我们可以先把所有数都按\(a_i\)排序一遍,这样考虑每个位置\(i\)的时候只需要考虑它前面的贡献即可
接下来我们递归处理区间\([1, n]\)。
设分治中心为\(mid\),cdq分治的主要思想递归处理每一段区间,只考虑过分治中心的贡献。
同时,我们采用归并排序的思想,保证每一次统计答案的时候区间\([l, mid]\)和\([mid +1, r]\)内的元素的\(b_i\)都是相对有序的
这样我们只需要用两个指针扫一遍,同时用树状数组来维护一下\(c_i\)即可
好像说的挺抽象的,貌似直接看代码会好很多?
void cdq(int l, int r) { if(l >= r) return ;//区间不合法 int mid = l + r >> 1; cdq(l, mid); cdq(mid + 1, r);//递归下去处理子区间,处理完之后保证区间内的bi相对有序 int nl = l, nr = mid + 1, top = l - 1, sum = 0;//使用两个指针来归并本区间 while(nl <= mid || nr <= r) {//st数组记录的时把两端区间按bi大小合并后的值 if((nr > r) || (nl <= mid && a[nl].b <= a[nr].b)) t.add(a[nl].c, a[nl].w), st[++top] = a[nl++];//用树状数组维护ci的贡献 else a[nr].id += t.query(a[nr].c ), st[++top] = a[nr++];//直接查询即可 } for(int i = l; i <= mid; i++) t.add(a[i].c, -a[i].w);//把左边区间的影响消除 for(int i = l; i <= r; i++) a[i] = st[i];//按bi排序 }
然而有一种非常恶心的情况:即\(a_i = a_j, b_i = b_j, c_i = c_j\)
他们内部的贡献往往是不好考虑的,一个最直观的想法是直接把这些相同的数看成一个,统计答案的时候直接加上他们的数量即可
模板
#include<bits/stdc++.h> #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++) using namespace std; const int maxn = 2e5 + 10; char buf[(1 << 22)], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } char obuf[1<<24], *o=obuf; void print(int x) { if(x > 9) print(x / 10); *o++= x % 10 + '0'; } int n, ans[maxn]; struct array { int a, b, c, id, w; bool operator == (const array &rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; } bool operator < (const array &rhs) const { return(a == rhs.a ? (b == rhs.b ? c < rhs.c : b < rhs.b) : a < rhs.a); } }a[maxn], st[maxn]; struct node { #define lb(x) (x & (-x)) int t[maxn], lim; void add(int x, int v) { while(x <= lim) t[x] += v, x += lb(x); } int query(int x) { int ans = 0; while(x) ans += t[x], x -= lb(x); return ans; } }t; void cdq(int l, int r) { if(l >= r) return ; int mid = l + r >> 1; cdq(l, mid); cdq(mid + 1, r); int nl = l, nr = mid + 1, top = l - 1, sum = 0; while(nl <= mid || nr <= r) { if((nr > r) || (nl <= mid && a[nl].b <= a[nr].b)) t.add(a[nl].c, a[nl].w), st[++top] = a[nl++]; else a[nr].id += t.query(a[nr].c ), st[++top] = a[nr++]; } for(int i = l; i <= mid; i++) t.add(a[i].c, -a[i].w); for(int i = l; i <= r; i++) a[i] = st[i]; } int main() { n = read(); t.lim = read(); for(int i = 1; i <= n; i++) a[i].a = read(), a[i].b = read(), a[i].c = read(), a[i].w = 1; stable_sort(a + 1, a + n + 1); int num = 1; for(int i = 2; i <= n; i++){ if(a[i] == a[num]) a[num].w++; else a[++num] = a[i]; } cdq(1, num); for(int i = 1; i <= num; i++) ans[a[i].id + a[i].w - 1] += a[i].w; for(int i = 0; i < n; i++) print(ans[i]), *o++ = '\n'; fwrite(obuf, o-obuf, 1 , stdout); return 0; }
上一篇: 懒加载预加载(图片)