Blackops

初心易得，始终难守

0%

CDQ分治学习

发表于 分类于 ，

一直很想学$CDQ$分治，多次尝试都是看到一半看不懂放弃了(弱比就是这样的吧……)，由于最近数据库作业天天要上机，但实际上也写的差不多了，就还是没放弃想继续学习一波这个高级分治姿势。

网上看了很多人的博客，发现$CDQ$分治中比较重要的就是序这个东西，因为有了序才能不重复不遗漏地统计贡献，比如最简单的归并法求逆序对，就是分治的应用之一，这个问题是一个二维偏序问题，如果把下标设为$i$，值设为$a[i]$，那么我们求的就是 $i \lt j,a[i] \gt a[j]$的个数，第一维是下标，第二维是值，显然给定的数组下标是递增的，即第一维已经排好了，那么可以直接扫描线的思想一遍从左到右扫过去用树状数组统计每一个元素值右边的个数再相加即可。但是分治怎么做呢？假如我们已经处理好了左区间$[l,m]$,$[m+1,r]$，那么对于每一个$a[j], j \in [m+1,r]$，只要统计出左区间大于$a[j]$的数的个数即可，如果在对左右区间分治处理完毕之后，顺便将左右区间分别归并排序一下，这样一来个数就可以直接得到为：$m-i+1$。

POJ 2299统计逆序对模板题
这里的$CDQ$遵循的序就是下标
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos (-1.0);
const int N = 500010;
int arr[N], temp[N];
LL ans;

void CDQ (int l, int r)
{
    if (l >= r)
        return ;
    int mid = MID (l, r);
    CDQ (l, mid);
    CDQ (mid + 1, r);
    int i = l, j = mid + 1;
    int sz = l;
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
            temp[sz++] = arr[i++];
        else
        {
            ans += (LL)(mid - i + 1);
            temp[sz++] = arr[j++];
        }
    }
    while (i <= mid)
        temp[sz++] = arr[i++];
    while (j <= r)
        temp[sz++] = arr[j++];
    for (int i = l; i <= r; ++i)
        arr[i] = temp[i];
}
int main (void)
{
    int n, i;
    while (~scanf ("%d", &n) && n)
    {
        for (i = 1; i <= n; ++i)
            scanf ("%d", arr + i);
        ans = 0;
        CDQ (1, n);
        printf ("%lld\n", ans);
    }
    return 0;
}

还有一道类似的题：牛客练习赛4 A.Laptop
题意就是统计每一个位置的元素与其前面的元素可以形成的顺序对有多少个，输出顺序对不为$0$的位置个数。
实际上跟上一题一样，只是求的是每一个位置的顺序对，且第一维第二维均无序，由于是顺序对，先按第一维从小到大排序，然后再在第二维上$CDQ$分治一波，统计的时候算出对应位置可形成的顺序对个数即可。
这里$CDQ$遵循的序就是第一维的值
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct info
{
    int a, b, id;
    bool operator<(const info &rhs)const {
        return b < rhs.b;
    }
} arr[N], temp[N];
int ans[N];

void CDQ(int l, int r)
{
    if (l >= r)
        return ;
    int mid = MID(l, r);
    CDQ(l, mid);
    CDQ(mid + 1, r);
    int i = l, j = mid + 1;
    int sz = l;
    while (i <= mid && j <= r)
    {
        if (arr[i] < arr[j])
        {
            ans[arr[i].id] += (r - j + 1);
            temp[sz++] = arr[i++];
        }
        else
        {
            temp[sz++] = arr[j++];
        }
    }
    while (i <= mid)
        temp[sz++] = arr[i++];
    while (j <= r)
        temp[sz++] = arr[j++];
    for (int i = l; i <= r; ++i)
        arr[i] = temp[i];
}
int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d%d", &arr[i].a, &arr[i].b);
        arr[i].id = i;
    }
    sort(arr + 1, arr + 1 + n, [](info a, info b) {return a.a < b.a;});
    CDQ(1, n);
    printf("%d\n", count_if(ans + 1, ans + 1 + n, [](int x) {return x != 0;}));
    return 0;
}

然后二维的$CDQ$分治还可以拓展一下，可以解决单点修改区间求和这种问题（虽然明显用$BIT$更简单）
假设给定一个具有初值的数组，然后可以对齐进行单点更新，区间求和操作，那么这里的序就是操作的时间顺序，显然能对询问产生影响的，只可能是询问之前所做的更新操作，那么这里就可以按照“时间”分治，将单点更新和询问均变为操作，数组的初值也变成单点更新操作即可，那么如何分治呢？显然$[l,m]$区间的更新对$[m+1,r]$的询问影响只能是更新点在询问范围之内的，但是如何简单地统计是一个问题，这里可以将询问拆成差分形式：$sum(l,r) = sum(1,r)-sum(1,l-1)$，这样就可以用一个变量统计出前缀和，然后根据询问是左端点还是右端点，在对应的询问编号记录点上加加减减。当然，如果序相同的话要更新优先，这个也是显然的
洛谷 P3374
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos (-1.0);
const int N = 500010;
const int M = 500010;
struct query
{
    int x, v, qid, type;
    bool operator< (const query &rhs)const {
        return x < rhs.x || (x == rhs.x && type < rhs.type);
    }
} Q[N + M * 2], temp[N + M * 2];
int ans[N];

void CDQ (int l, int r)
{
    if (l >= r)
        return ;
    int mid = MID (l, r);
    CDQ (l, mid);
    CDQ (mid + 1, r);
    int i = l, j = mid + 1;
    int sz = l, sum = 0;
    while (i <= mid && j <= r)
    {
        if (Q[i] < Q[j])
        {
            if (Q[i].type == 1)
                sum += Q[i].v;
            temp[sz++] = Q[i++];
        }
        else
        {
            if (Q[j].type == 2)
                ans[Q[j].qid] -= sum;
            else if (Q[j].type == 3)
                ans[Q[j].qid] += sum;
            temp[sz++] = Q[j++];
        }
    }
    while (i <= mid)
        temp[sz++] = Q[i++];
    while (j <= r)
    {
        if (Q[j].type == 2)
            ans[Q[j].qid] -= sum;
        else if (Q[j].type == 3)
            ans[Q[j].qid] += sum;
        temp[sz++] = Q[j++];
    }
    for (int i = l; i <= r; ++i)
        Q[i] = temp[i];
}
int main (void)
{
    int n, m, i;
    scanf ("%d%d", &n, &m);
    int tot = 0, qid = 0;
    for (i = 1; i <= n; ++i)
    {
        int v;
        scanf ("%d", &v);
        Q[++tot] = {i, v, 0, 1};
    }
    int ops;
    for (i = 1; i <= m; ++i)
    {
        scanf ("%d", &ops);
        if (ops == 1)
        {
            int x, k;
            scanf ("%d%d", &x, &k);
            Q[++tot] = {x, k, 0, 1};
        }
        else
        {
            int l, r;
            scanf ("%d%d", &l, &r);
            Q[++tot] = {l - 1, 0, ++qid, 2};
            Q[++tot] = {r, 0, qid, 3};
        }
    }
    CDQ (1, tot);
    for (i = 1; i <= qid; ++i)
        printf("%d\n", ans[i]);
    return 0;
}