这是一个比较人类智慧的算法，尽管它大多数时候都不是出题人想要考察的算法，但是绝大部分时候出题人都没办法卡掉你然后愤然强制在线。
在怎样的情况下才能使用 cdq 分治？一般有如下情况：
-
解决点对问题 \((i,j)\)。
在算点对贡献时，我们将贡献拆成三类
- \(i\in[1,mid],j\in[1,mid]\)
- \(i\in[1,mid],j\in[mid + 1, n]\)
- \(i\in[mid + 1,n],j\in[mid + 1, n]\)
此时我们发现可以将整个序列拆成两段，\((1,mid)\) 和 \((mid + 1, n)\)。我们可以递归地处理第一种和第三种点对，我们只要想办法合并信息处理第二类点对即可。
-
动态规划的优化和转移
这类题目一般是一维的 dp 式，时间复杂度达到了 \(n^2\) 级别，而我们有时可以用 cdq 分治做到 \(\log n\) 转移。
下文我们将提到这种应用。
-
把动态问题转换成静态问题
这是老套路了，有的题目会有修改操作和查询操作，我们可以离线询问，对时间序列分治，下文也会给出详细解释。
点对问题
经典问题，对每个 \(d\in[0,n)\) 求 满足 \(a_j\le a_i,b_j\le b_i,c_j\le c_i,i\not=j\) 的 \(j\) 的个数有 \(d\) 个 的 \(i\) 的个数。我们发现这是一个三维偏序，先考虑按某一维排序消去一个影响。
在 solve(l, r) 中，假设我们已经解决了 solve(l, mid) 和 solve(mid + 1, r)，问题来到了如何求 \(l \le j \le mid,mid + 1\le i\le r\) 这种点对上。由于排序过，左侧点不再对右侧点做出贡献。因此只要算出有多少满足 \(b_j \le b_i,c_j\le c_i\) 的 \(j\) 的数量。
先将区间内部的点排序，那么对于每个 \(i\)，对应的可能的答案是一段前缀，接下来就是如何统计在这个前缀中满足 \(c_j \le c_i\) 的数量，这里显然使用树状数组。
以下是代码，注意一些精细化实现
const int N = 1e5 + 5;
int n, k, cnt, f[N];
struct node {
int a, b, c, val, ans;
node() {}
node(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
il bool operator!=(const node& _eps) {return a ^ _eps.a || b ^ _eps.b || c ^ _eps.c; }
}o[N], lsh[N];
struct BIT {
#define lowbit(x) (x & (-x))
int tr[N << 1], n;
il void resize(const unsigned& lim) { n = lim; }
il void add(int p, int v) { for(; p <= n; p += lowbit(p)) tr[p] += v; }
il int query(int p) { int sum = 0; for(; p; p -= lowbit(p)) sum += tr[p]; return sum; }
#undef lowbit
} bit;
il bool cmp1(const node& x, const node& y) { return x.a ^ y.a ? x.a < y.a : (x.b ^ y.b ? x.b < y.b : x.c < y.c); }
il bool cmp2(const node& x, const node& y) { return x.b ^ y.b ? x.b < y.b : x.c < y.c; }
il void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid); solve(mid + 1, r);
sort(lsh + l, lsh + mid + 1, cmp2); sort(lsh + mid + 1, lsh + r + 1, cmp2);
int ul = l;
for (int i = mid + 1; i <= r; ++i) {
while (ul <= mid && lsh[ul].b <= lsh[i].b) bit.add(lsh[ul].c, lsh[ul].val), ++ul;
lsh[i].ans += bit.query(lsh[i].c);
}
for (int i = l; i < ul; ++i) bit.add(lsh[i].c, -lsh[i].val);
}
int main() {
read(n), read(k);
for (int i = 1; i <= n; ++i) o[i] = node(read(), read(), read());
sort(o + 1, o + n + 1, cmp1);
for (int i = 1; i <= n; ++i) {
if (o[i] != o[i - 1]) lsh[++cnt] = o[i];
++lsh[cnt].val;
}
bit.resize(200000);
solve(1, cnt);
for (int i = 1; i <= cnt; ++i) f[lsh[i].ans + lsh[i].val - 1] += lsh[i].val;
for (int i = 0; i < n; ++i) write(f[i]);
return 0;
}
当然我们在上述提到过 cdq 分治可以化动为静，因此我们可以将点对变成动态的。比如下面这道例题
[CQOI2011] 动态逆序对
给定 \(a_i\)，同时给定一个删除元素的顺序，问删除某个元素之前逆序对的个数。
依题意，在删除第 \(i\) 个点之前，有效的点对必须满足 \(tim_j > tim_i,(i<j\land a_i > a_j) \lor (i > j \and a_i<a_j)\)。
这不经典三维偏序？贴出另一种 cdq 分治实现方式
点我看代码
const int N = 1e5 + 5;
int n, m;
ll Ans;
struct node {
int t, v, i, ans;
node(){ ans = 0; }
node(int _t, int _v, int _i) : t(_t), v(_v), i(_i) {}
} a[N];
struct BIT {
#define lowbit(x) (x & (-x))
int tr[N], n;
il void resize(const int lim) { n = lim; }
il void add(int p, const int v) { for(; p <= n; p += lowbit(p)) tr[p] += v; }
il int query(int p) { int sum = 0; for (; p; p -= lowbit(p)) sum += tr[p]; return sum; }
#undef lowbit
}bit;
il bool cmp1(const node& x, const node& y) { return x.t < y.t; }
il bool cmp2(const node& x, const node& y) { return x.v < y.v; }
il bool cmp3(const node& x, const node& y) { return x.i < y.i; }
il void solve(int l, int r) {
if (r - l == 1) return;
int mid = (l + r) >> 1;
solve(l, mid); solve(mid, r);
int i = l + 1, j = mid + 1;
while (i <= mid) {
while (a[i].v > a[j].v && j <= r) bit.add(a[j].t, 1), ++j;
a[i].ans += bit.query(m) - bit.query(a[i].t); ++i;
}
i = l + 1, j = mid + 1;
while (i <= mid) {
while (a[i].v > a[j].v && j <= r) bit.add(a[j].t, -1), ++j;
++i;
}
i = mid; j = r;
while (j > mid) {
while(a[j].v < a[i].v && i > l) bit.add(a[i].t, 1), --i;
a[j].ans += bit.query(m) - bit.query(a[j].t); --j;
}
i = mid; j = r;
while (j > mid) {
while(a[j].v < a[i].v && i > l) bit.add(a[i].t, -1), --i;
--j;
}
sort(a + l + 1, a + r + 1, cmp2);
}
int rnk[N];
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) read(a[i].v), rnk[a[i].v] = i;
for (int i = 1; i <= m; ++i) a[rnk[read()]].t = i;
for (int i = 1; i <= n; ++i) if (!a[i].t) a[i].t = m;
bit.resize(n);
for (int i = 1; i <= n; ++i) {
Ans += bit.query(n) - bit.query(a[i].v);
bit.add(a[i].v, 1);
}
for (int i = 1; i <= n; ++i) bit.add(a[i].v, -1);
solve(0, n);
sort(a + 1, a + n + 1, cmp1);
for (int i = 1; i <= m; ++i) {
write(Ans); Ans -= a[i].ans;
}
return 0;
}
我也不知道为什么，反正我用板子题写法没过，换成这种过了。