Chaos Slover 补档计划 - CDQ分治

2015.11.24 09:51 Tue| 9 visits oi_2016| ChaosSlover补档计划| Text

CDQ 分治

其实这个分治的思想虽然说起来很简单,但是实际上并不好理解。

考虑一个三维偏序的模型,如果正常去做一定需要用两维树结构去维护其中的两维,查询剩下的一维。然而通过 CDQ 分治我们可以减少一维树上结构。

CDQ 分治的关键就是保证分治区间内部的有序性。

JDFZOJ2764 二维LCS

位置在区间 (mid+1, r) 中的元素可以被位置在 (l, mid) 的元素更新。因此如果我们先分治处理出区间 (l, mid) 内的答案,就可以先去更新一下区间 (mid+1, r) 中的元素,之后再递归处理区间 (mid+1, r) 的时候就只需要考虑这个区间内部产生的影响了。

我们更新 (l, r) 区间的时候可以先保证 (l, mid) 内和 (mid+1, r) 内的元素都关于 x 坐标递增,再用树状数组去维护 y 坐标范围内的最大值。

时间复杂度可以降到 O(n*log n)。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 20005

struct data
{
    int id, x, y;
    bool operator <(data &p) const { return id < p.id; }
} p[N], temp[N];

int n, f[N], fen[N];

inline bool cmp(const data &p, const data &q)
{
    return p.x == q.x ? p.y < q.y : p.x < q.x;
}

void insert(int x, int d)
{
    for (int i = x; i < N; i += i & -i)
        fen[i] = max(fen[i], d);
}

void erase(int x)
{
    for (int i = x; i < N; i += i & -i)
        fen[i] = 0;
}

int query(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re = max(re, fen[i]);
    return re;
}

void cdq(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l, tl = l, tr = mid + 1; i <= r; ++i)
        if (p[i].id <= mid) temp[tl++] = p[i];
        else temp[tr++] = p[i];
    for (int i = l; i <= r; ++i)
        p[i] = temp[i];
    cdq(l, mid);
    for (int i = l, j = mid + 1; j <= r; ++j)
    {
        while (i <= mid && p[i].x < p[j].x) insert(p[i].y, f[p[i].id]), ++i;
        f[p[j].id] = max(f[p[j].id], query(p[j].y - 1) + 1);
    }
    for (int i = l; i <= mid; ++i)
        erase(p[i].y);
    cdq(mid + 1, r);
    sort(p + l, p + r + 1, cmp);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
    sort(p + 1, p + n + 1, cmp);
    f[1] = 1;
    cdq(1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

BZOJ3295 动态逆序对

论好好读题的重要性——删除的是元素而不是某一个位置的元素!我这个 ** 在这里调了半天,样例还过了!

可以先用树状数组预处理出总的逆序对个数和删除每一个位置的元素会减少的逆序对个数。考虑删除了某一个元素之后,再删除其他元素的时候将会减少的逆序对个数可能会减少(这句话怎么这么乱啊),于是我们需要求出删除每一个元素时减少的逆序对个数的减少量(我彻底被这句话绕晕啦)。

然后上 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
 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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m, a[N], q[N], pos[N], bit1[N], bit2[N];
long long sum, ans[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct data
{
    int id, x, y;

    data() {}
    data(int _id, int _x, int _y) : id(_id), x(_x), y(_y) {}

    bool operator <(const data &d) const
    {
        return x < d.x;
    }
} p[N], temp[N];

void insert1(int x, int y)
{
    for (int i = x; i; i -= i & -i)
        bit1[i] += y;
}

int query1(int x)
{
    int re = 0;
    for (int i = x; i <= n; i += i & -i)
        re += bit1[i];
    return re;
}

void insert2(int x, int y)
{
    for (int i = x; i <= n; i += i & -i)
        bit2[i] += y;
}

int query2(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += bit2[i];
    return re;
}

void cdq(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l, tl = l, tr = mid + 1; i <= r; ++i)
        if (p[i].id <= mid) temp[tl++] = p[i];
        else temp[tr++] = p[i];
    for (int i = l; i <= r; ++i)
        p[i] = temp[i];
    cdq(l, mid);
    for (int i = l, j = mid + 1; j <= r; ++j)
    {
        while (i <= mid && p[i].x < p[j].x)
            insert1(p[i++].y, 1);
        ans[p[j].x] -= query1(p[j].y);
        if (j == r)
            while (i <= mid) insert1(p[i++].y, 1);
    }
    for (int i = mid, j = r; j >= mid + 1; --j)
    {
        while (i >= l && p[i].x > p[j].x)
            insert2(p[i--].y, 1);
        ans[p[j].x] -= query2(p[j].y);
        if (j == mid + 1)
            while (i >= l) insert2(p[i--].y, 1);
    }
    for (int i = l; i <= mid; ++i)
        insert1(p[i].y, -1), insert2(p[i].y, -1);
    cdq(mid + 1, r);
    sort(p + l, p + r + 1);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read(), pos[a[i]] = i;
        sum += query1(a[i]);
        ans[i] = a[i] - i + query1(a[i]) * 2;
        insert1(a[i], 1);
    }
    memset(bit1, 0, sizeof bit1);
    for (int i = 1; i <= m; ++i)
        q[i] = pos[read()], p[i] = data(i, q[i], a[q[i]]);
    sort(p + 1, p + m + 1);
    cdq(1, m);
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", sum), sum -= ans[q[i]];
    return 0;
}

BZOJ2683&1176 [Balkan2007]Mokia

今天这题做了两遍,真是醉了。把一个询问操作拆成四个,询问和修改一起跑,然后就是简单的 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
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 N 200005

int s, w, tot, q, ans[N], bit[N * 10];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct data
{
    int type, id, x, y, z;
    data() {}
    data(int _type, int _id, int _x, int _y, int _z)
    : type(_type), id(_id), x(_x), y(_y), z(_z) {}
    bool operator <(const data &d) const
    { return x < d.x; }
} d[N], temp[N];

void insert(int x, int y)
{
    for (int i = x; i <= w; i += i & -i)
        bit[i] += y;
}

int query(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += bit[i];
    return re;
}

void cdq(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l, tl = l, tr = mid + 1; i <= r; ++i)
        if (d[i].id <= mid) temp[tl++] = d[i];
        else temp[tr++] = d[i];
    for (int i = l; i <= r; ++i)
        d[i] = temp[i];
    cdq(l, mid);
    for (int i = l, j = mid + 1; j <= r; ++j)
    {
        if (d[j].type == 2)
        {
            while (i <= mid && d[i].x <= d[j].x)
            {
                if (d[i].type == 1) insert(d[i].y, d[i].z);
                ++i;
            }
            ans[abs(d[j].z)] += query(d[j].y) * (d[j].z / abs(d[j].z));
        }
        if (j == r)
            while (i > l)
                if (d[--i].type == 1) insert(d[i].y, -d[i].z);
    }
    cdq(mid + 1, r);
    sort(d + l, d + r + 1);
}

int main()
{
    cin >> s >> w;
    int x = 0;
    while ((x = read()) != 3)
    {
        if (x == 1)
        {
            int x = read(), y = read(), z = read();
            ++tot, d[tot] = data(1, tot, x, y, z);
        }
        else
        {
            int x1 = read(), y1 = read(), x2 = read(), y2 = read();
            ans[++q] = s * (x2 - x1 + 1) * (y2 - y1 + 1);
            ++tot, d[tot] = data(2, tot, x1 - 1, y2, -q);
            ++tot, d[tot] = data(2, tot, x2, y1 - 1, -q);
            ++tot, d[tot] = data(2, tot, x2, y2, q);
            ++tot, d[tot] = data(2, tot, x1 - 1, y1 - 1, q);
        }
    }
    sort(d + 1, d + tot + 1);
    cdq(1, tot);
    for (int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ2716 [Violet 3]天使玩偶

每一层分治里面套四个树状数组,分别维护四个方向的询问。

我宁可去用 K-DTree 去 AC 这道题。

BZOJ3262 陌上花开

其实边界的判断并不麻烦(或者说并不需要怎么判断)。首先需要把相同的花合并起来,然后排序的时候如果第二维相同需要按照第三维排序,这样就可以保证只有前面的花能够更新后面的花了。

然而我这个逗逼最后统计答案的时把 d[i].id 写成了 i 结果 WA 了半天还不知道是为什么。

接下来就要写【货币兑换】了啊哈哈哈哈!!!

 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
#include <bits/stdc++.h>
using namespace std;

#define N 200005

vector<pair<int, pair<int, int> > > v;
int n, k, bit[N], ans[N], sum[N]; 

struct data
{
    int id, x, y, z;
    data() {}
    data(int _id, int _x, int _y)
    : id(_id), x(_x), y(_y), z(1) {}
    bool operator <(const data &d) const
    { return x == d.x ? y < d.y : x < d.x; }
} d[N], temp[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void insert(int x, int y)
{
    for (int i = x; i <= k; i += i & -i)
        bit[i] += y;
}

int query(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += bit[i];
    return re;
}

void cdq(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l, tl = l, tr = mid + 1; i <= r; ++i)
        if (d[i].id <= mid) temp[tl++] = d[i];
        else temp[tr++] = d[i];
    for (int i = l; i <= r; ++i)
        d[i] = temp[i];
    cdq(l, mid);
    for (int i = l, j = mid + 1; j <= r; ++j)
    {
        while (i <= mid && d[i].x <= d[j].x)
            insert(d[i].y, d[i].z), ++i;
        ans[d[j].id] += query(d[j].y);
        if (j == r)
            while (i > l)
                --i, insert(d[i].y, -d[i].z);
    }
    cdq(mid + 1, r);
    sort(d + l, d + r + 1);
}

int main()
{
    cin >> n >> k;
    for (int x, y, z, i = 1; i <= n; ++i)
        x = read(), y = read(), z = read(),
        v.push_back(make_pair(x, make_pair(y, z)));
    sort(v.begin(), v.end());
    int tot = 0;
    for (int i = 0; i < (int)v.size(); ++i)
    {
        if (i && v[i] == v[i - 1]) ++d[tot].z;
        else 
            ++tot, d[tot] = data(tot, v[i].second.first, v[i].second.second);
    }
    sort(d + 1, d + tot + 1);
    cdq(1, tot);
    for (int i = 1; i <= tot; ++i)
        sum[ans[d[i].id] + d[i].z - 1] += d[i].z;
    for (int i = 0; i < n; ++i)
        printf("%d\n", sum[i]);
    return 0;
}

BZOJ1492 [NOI2007]货币兑换Cash

唔,虽然写的是 CDQ 分治,但我仍然调了一晚上……

让我调了一晚上的事情:

  1. 对修改要维护一个上凸包,因此对于询问我们是要保证斜率递减的。
  2. 排序的时候如果两个点的横坐标太近我们要按照纵坐标排序(其实这里不排序也没有关系),在计算斜率的时候如果横坐标太近我们要返回无穷(正无穷和负无穷都可以 AC)。
  3. 如果前两点都没有注意的话,CDQ 分治还是会给你 60-70 分的,并且错误的会是中间的测试点。
  4. 一定要先维护出来上凸包……我这个 SX 边询问边维护凸包还沾沾自喜的……

其实代码看起来挺简单的。嗯,挺简单的。

首先我们要膜拜一下 CDQ 神牛的论文。设 Xi 表示在第 i 天最多能够兑换到 A 券的数量,Yi 表示在第 i 天最多能够兑换到 B 券的数量,Fi 表示第 i 天操作结束时能够获得的最大的金钱数目。可以列出来等式:

这就是一个斜率优化的形式。对于 $X_j<X_k$,若选择 j 比选择 k 更优,可以得到

因此我们对点 $(X_i,Y_i)$ 维护一个上凸包,每一次询问就去找凸包中满足和前面的点之间斜率大于 $-\frac{A_i}{B_i}$ 的最大的 j 来更新答案。

可惜,X 不单调,Y 也不单调,A 和 B 都不单调。不单调啊不单调,Splay 树维护凸包。

听 PoPoQQQ 大爷说 Splay 及其麻烦,于是就可以写 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
69
70
71
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n;
double s, a[N], b[N], rate[N], p[N], f[N], x[N], ans;

struct data
{
    int id; double x;
    data() {}
    data(int _id, double _x) : id(_id), x(_x) {}
    bool operator <(const data &d) const
    { return x > d.x; }
} d[N], temp[N];

bool cmp(const data &d1, const data &d2)
{
    if (fabs(x[d1.id] - x[d2.id]) < 1e-9)
        return rate[d1.id] > rate[d2.id];
    return x[d1.id] < x[d2.id];
}

inline double getk(int p1, int p2)
{
    if (fabs(x[p1] - x[p2]) < 1e-9) return 1e9;
    return (x[p1] / rate[p1] - x[p2] / rate[p2]) / (x[p1] - x[p2]);
}

void cdq(int l, int r)
{
    if (l == r) { f[l] = max(f[l], f[l - 1]); x[l] = f[l] * p[l]; return; }
    int mid = (l + r) >> 1;
    for (int tl = l, tr = mid + 1, i = l; i <= r; ++i)
        if (d[i].id <= mid) temp[tl++] = d[i];
        else temp[tr++] = d[i];
    for (int i = l; i <= r; ++i)
        d[i] = temp[i];
    cdq(l, mid);
    vector<int> v; vector<double> k;
    v.push_back(d[l].id);
    for (int i = l + 1; i <= mid; ++i)
    {
        while (k.size() && getk(d[i].id, v.back()) > k.back())
            v.pop_back(), k.pop_back();
        k.push_back(getk(d[i].id, v.back())); v.push_back(d[i].id);
    }
    int t = 0;
    for (int i = mid + 1; i <= r; ++i)
    {
        while (t < (int)k.size() && k[t] > d[i].x) ++t;
        f[d[i].id] = max(f[d[i].id],
            x[v[t]] * a[d[i].id] + x[v[t]] / rate[v[t]] * b[d[i].id]);
    }
    cdq(mid + 1, r);
    sort(d + l, d + r + 1, cmp);
}

int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf%lf", &a[i], &b[i], &rate[i]),
        d[i] = data(i, -a[i] / b[i]),
        p[i] = rate[i] / (a[i] * rate[i] + b[i]);
    sort(d + 1, d + n + 1);
    f[0] = s; cdq(1, n);
    cout << fixed << setprecision(3) << f[n] << endl;
    return 0;
}