RenaMoe's Blog

念念不忘，必有回响

0%

总结 CDQ分治

发表于 更新于 分类于 ， Valine：

咕了几个月的玩意。。。

先贴几个板子，总结后面补

P1908 逆序对

P2274 树状数组1

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
struct Node {
    ll id, val, type;
    bool operator <(const Node &x) const {
        return id == x.id ? type < x.type : id < x.id;
    }
};
void CDQ(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) / 2;
    CDQ(l, mid), CDQ(mid+1, r);
    int x = l, y = mid+1, k = l;
    ll sum = 0;
    while (x <= mid && y <= r) {
        if (a[x] < a[y]) {
            if (a[x].type == 1)
                sum += a[x].val;
            t[k++] = a[x++];
        }
        else {
            if (a[y].type == 2)
                ans[a[y].val] -= sum;
            if (a[y].type == 3)
                ans[a[y].val] += sum;
            t[k++] = a[y++];
        }
    }
    while (x <= mid)
        t[k++] = a[x++];
    while (y <= r) {
        if (a[y].type == 2)
            ans[a[y].val] -= sum;
        if (a[y].type == 3)
            ans[a[y].val] += sum;
        t[k++] = a[y++];
    }
    for (int i = l; i <= r; i++)
        a[i] = t[i];
}

......
for (int i = 1, t; i <= n; i++)
    t = read(), a[++cnta] = (Node){i, t, 1};
for (int i = 1; i <= m; i++) {
    ll c = read(), x = read(), y = read();
    if (c == 1)
        a[++cnta] = (Node){x, y, 1};
    else {
        a[++cnta] = (Node){x-1, ++cntq, 2};
        a[++cnta] = (Node){y, cntq, 3};
    }
}

P3810 陌上花开

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
struct Node {
    int a, b, c, cnt, ans;
    bool operator ==(const Node &t) const {
        return a == t.a && b == t.b && c == t.c;
    }
};

int n, bn, maxk;
int cnt[N];
Node a[N], b[N];

inline bool cmp1d(Node x, Node y) {
    if (x.a == y.a)
        return x.b == y.b ? x.c < y.c : x.b < y.b;
    return x.a < y.a;
}

inline bool cmp2d(Node x, Node y) {
    return x.b == y.b ? x.c < y.c : x.b < y.b;
}

struct Bit_tree {...} tr;

void CDQ(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    CDQ(l, mid), CDQ(mid+1, r);
    sort(a+l, a+mid+1, cmp2d);
    sort(a+mid+1, a+r+1, cmp2d);
    int i = l, j = mid + 1, k = l;
    while (j <= r) {
        while (i <= mid && a[i].b <= a[j].b)
            tr.add(a[i].c, a[i].cnt), i++;
        a[j].ans += tr.query(a[j].c), j++;
    }
    for (j = l; j < i; ++j)
        tr.add(a[j].c, -a[j].cnt);
}

inline void main() {
    read(bn), read(maxk);
    for (int i = 1; i <= bn; ++i)
        read(b[i].a), read(b[i].b), read(b[i].c);
    sort(b+1, b+bn+1, cmp1d);
    for (int i = 1; i <= bn; ++i) {
        if (b[i] == b[i-1])
            a[n].cnt++;
        else 
            a[++n] = b[i], a[n].cnt++;
    }
    CDQ(1, n);
    for (int i = 1; i <= n; ++i)
        cnt[a[i].ans + a[i].cnt - 1] += a[i].cnt;
    for (int i = 0; i < bn; ++i)
        printf("%d\n", cnt[i]);
}