gyro永不抽风！ - CDQ
type: channel
link: https://gallery.gyrojeff.top/index.php/tag/CDQ/
items: Archived | 306-14-CDQ分治-陌上花开

Archived | 306-14-CDQ分治-陌上花开
type: item
date: 2020-02-28T15:39:00+00:00
description: 题目大意 对于给遗传给定的序列： $$ (x,y,z)_1, (x,y,z)_2, (x,y,z)_3, \cdots, (x,y,z)_n $$ 求： $$ \sum_{x_i < x_j,~y_i < y_j,~z_i<z_j,~i ≠j}1 $$ 题解： CDQ分治，顾名思义就是要进行分治，但是它可以解决比普通分治更多的问题。CDQ分治的整体思想，是： 对于一个需要解决问题的区间$[l,r)$，将其一分为二，变为$[l,mid),[mid,r)$。 对于这两个被分开的区间，分别进行递归解决。 完成递归解决之后，计算左边对右边的贡献（有的时候可能要计算右边对左边的计算或者互相都要算） 完成，统计答案。 在这道题当中，需要解决的是三维偏序的问题，而首先想到的是使用二维树状数组进行求逆序对，将这三维当中的两维当作下标，对最后一维求逆序对。但是这种做法显而易见，空间会爆掉，是开不下的。所以我们需要采取某种算法或者数据结构来代替树状数组的这意味空间。 在这里，就是用了CDQ分治。 首先解决第一维的问题：以第一维作为第一关键字，第二维作为第二关键字，第三维作为第三关键字，进行排序。比较函数如下： bool cmp1(Point a, Point b) { if (a.x == b.x && a.y == b.y) return a.z < b.z; if (a.x == b.x) return a.y < b.y; return a.x < b.x; } 在进行排序之后，就保证了整个序列单调不下降。 随后进行CDQ分治：solve(0,n) solve(0,mid)，solve(mid, n) 计算左边对右边的影响（原因：整个序列对于第一维变量单调不下降，所以右边的大数无法对小数产生答案上的贡献） 对$[l,mid),[mid,r)$分别进行以第二维作为第一关键字，第三维作为第二关键字的排序： bool cmp2(Point a, Point b) { if (a.y == b.y) return a.z < b.z; return a.y < b.y; } 注意，这里是直接对原数组进行排序，而且实际上不会产生任何问题，因为被排序的两个子序列的这两个子问题，共同属于同一个问题，所以在进行其父亲问题的解决时还会进行重拍，届时并不会产生元素跨界问题。 进行双指针扫描，双指针扫描的目的就是直接使用树状数组对每个元素进行答案统计。 整个问题解决完毕。 但是其存在一定的问题：由于CDQ分治这里我们讨论过了，应该只需要计算左边对右边的影响，但是忽略了一种情况，就是两个元素完全相同，那么左右应该共享影响，但是这里是非常难做到的，所以对于输入的时候，直接进行去重操作，并且赋予每个元素重复次数的权值，方便计算。 注意：在统计答案的时候，会看到下式： ans[A[i].ans + A[i].cnt - 1] += A[i].cnt 这里还要加上A[i].cnt-1的原因其实也不难想到，就是去重的逆运算。 历届悲惨代码如下： 第一次（WA，0分，没有去重）： #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll, pair<ll, ll> > Point; const ll maxn = 200005; Point A[maxn]; ll n, K, ord[maxn], f[maxn], T[maxn], ans[maxn]; bool cmp(ll x, ll y) { return A[x].second < A[y].second; } ll lb(ll i) { return i & (-i); } void add(ll i, ll delta) { while (i <= K) { T[i] += delta; i += lb(i); } } ll sum(ll i) { ll ans = 0; while (i > 0) { ans += T[i]; i -= lb(i); } return ans; } // 左闭右开 void solve(ll left, ll right) { if (right - left == 1) return; ll mid = (right + left) / 2; solve(left, mid); solve(mid, right); for (ll i = left; i < right; i ++) ord[i] = i; sort(ord + left, ord + right, cmp); // 左边对右边的理想 for (ll i = left;…