NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【学习笔记】cdq 分治

posted on 2019-10-20 00:05:18 | under 学习笔记 |

由于太懒,我只学会了 cdq 分治解决逆序对问题。

例题 P3810

原理

cdq 分治: 对于一个区间 $[l,r]$进行操作时,先对 $[l,mid]$和 $[mid+1,r]$进行操作,然后统计 $[l,mid]$对 $[mid+1,r]$的影响,最终得到结果,这样的过程就是 cdq 分治。

偏序问题

考虑对于 $\forall i$,如何计算 $a_i\geq a_j,b_i\geq b_j,c_i\geq c_j$的 $j$的个数。

可以渐进地思考这个问题:

逆序对

直接搞个权值树状数组作为一个桶,然后从右到左扫一遍;或者归并排序统计答案即可。当然也可以用与解决顺序对问题。

二维偏序

如果是二维,考虑对一维的每个数构造数对 $(i,a_i)$,显然对于一个顺序对 $(a_i,a_j)$有 $i<j,a_i<a_j$,么按 $a$排序以后,就转化为了一维顺序对问题。

这样就得出了一个很重要的结论:在偏序问题中,只要有一位有序,那么就可以直接忽略这一维。这也为降维提供了可能性。

回到三维偏序问题,假设 $a$有序,那么就可以直接忽略 $a$的影响了;再考虑对 $b$进行类似于归并排序的处理,同时使用 cdq 分治,对 $c$构造一个权值树状数组,每次只需要统计 $c_j\leq c_i$的个数即可。

另外,还有两个坑点:

  1. 树状数组在每次归并排序完成之后必须清空,否则会不停加下去;
  2. $a,b,c$全部相等的情况需要特判处理。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 2e5 + 10;
struct _node {
    int a, b, c, ans;
} node[MAXN];
int cnt[MAXN];

bool cmp1(const _node &lhs, const _node &rhs) {
    if (lhs.a != rhs.a)
        return lhs.a < rhs.a;
    if (lhs.b != rhs.b)
        return lhs.b < rhs.b;
    return lhs.c < rhs.c;
}

bool cmp2(const _node &lhs, const _node &rhs) {
    return lhs.b < rhs.b;
}
//  cmp2 用于 cdq 分治

bool operator != (const _node &lhs, const _node &rhs) {
    return (lhs.a != rhs.a) || (lhs.b != rhs.b) || (lhs.c != rhs.c);
} 

int n, k, c[MAXK];

void add(int x, int val) {
    for ( ; x <= k; x += x & (-x))
        c[x] += val;
    return ;
}

int query(int x) {
    int res = 0;
    for ( ; x; x -= x & (-x))
        res += c[x];
    return res;
}

void cdq(int l, int r) {
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(node + l, node + mid + 1, cmp2);
    sort(node + mid + 1, node + r + 1, cmp2);
    int j = l;
    for (int i = mid + 1; i <= r; i++) {
        while (j <= mid && node[j].b <= node[i].b) {
            add(node[j].c, 1);
            j++;
        }
        node[i].ans += query(node[i].c);
    }
    while (--j >= l)
        add(node[j].c, -1);
//  attention!!
//  树状数组必须清空,否则凉凉
    return ;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d",&node[i].a, &node[i].b, &node[i].c);
    sort(node + 1, node + n + 1, cmp1);
    for (int i = n, j = n; i >= 1; i--) {
        while (node[i] != node[j])
            j--;
        node[i].ans += j - i;
        printf(" > %d\n", node[i].ans);
    }
//  attention!!
//  特判 i < j 且 a, b, c 全部相等的情况
//  原因:cdq(l, r) 中的第一个 while 会把所有相等的都跳过
    cdq(1, n);
    for (int i = 1; i <= n; ++i)
        cnt[node[i].ans]++;
    for (int i = 0; i < n; i++)
        printf("%d\n", cnt[i]);
    return 0;
}