分治算法

发表于 | 分类于 ， | 阅读次数：
本文字数： 14k | 阅读时长 ≈ 13 分钟

分治算法，顾名思义，分而治之。
分治算法，每次将区间减半，化为[l,mid],[mid+1,r]区间，再用解决的两个区间来跟新[l,r],非常典型的例子就是归并排序。
归并排序，每次对[l,mid],[mid+1,r]处理，然后$O(n)$合并两个数组，层数$O(logn)$,每层合并$O(n)$复杂度稳定$O(nlog(n))$。

CDQ分治

典型例题:
洛谷 3810 三维偏序
洛谷 3157 动态逆序对
本校OJ的某个题，链接失效很正常

三维偏序

三维逆序对是个很裸的题，直接对$x$排序，排序之后像归并排序一样，分治$y$，然后用树状数组更新$z$。就是把归并排序处理逆序对的方法从枚举变成了树状数组。
树状数组更新z其实也可以改成用cdq分治处理，换成其他$O(nlog(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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// luogu-judger-enable-o2
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid ((l + r) >> 1)
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define eb(x) emplace_back(x)
#define pb(x) emplace_back(x)
#define mem(a, b) memset(a, b, sizeof(a));

const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;

#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

//typedef __int128 LLL;

template<typename T>
void read(T &w) {//读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))
        w = w * 10 + (c & 15);
}

template<typename T>
void output(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    int ss[55], sp = 0;
    do
        ss[++sp] = x % 10;
    while (x /= 10);
    while (sp)
        putchar(48 + ss[sp--]);
}

LL bit[maxn + 1], n, k;

LL sum(int i) {
    LL s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, LL x) {
    while (i <= k) {
        bit[i] += x;
        i += i & -i;
    }
}

struct node {
    int x, y, z, ans, cnt;

    bool operator==(const node t) const {
        return x == t.x && y == t.y && z == t.z;
    }
} dat[maxn];

int ans[maxn];

bool cmp1(node &a, node &b) {
    if (a.x == b.x)return a.y == b.y ? a.z < b.z : a.y < b.y;
    return a.x < b.x;
}

bool cmp2(node &a, node &b) {
    return a.y == b.y ? a.z < b.z : a.y < b.y;
}

void cdq(int l, int r) {
    if (r == l)return;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(dat + l, dat + mid + 1, cmp2);
    sort(dat + mid + 1, dat + r + 1, cmp2);
    int j = mid + 1;
    int i = l;
    while (i <= mid && j <= r) {
        if (dat[i].y <= dat[j].y) {
            add(dat[i].z, dat[i].cnt);
            i++;
        } else {
            dat[j].ans += sum(dat[j].z);
            j++;
        }
    }
    while (i <= mid) {
        add(dat[i].z, dat[i].cnt);
        i++;
    }
    while (j <= r) {
        dat[j].ans += sum(dat[j].z);
        j++;
    }
    for (i = l; i <= mid; i++)add(dat[i].z, -dat[i].cnt);
}

int main() {
    f();
    read(n);
    read(k);
    k++;
    for (int i = 1; i <= n; i++) {
        read(dat[i].x);
        read(dat[i].y);
        read(dat[i].z);
    }
    sort(dat + 1, dat + n + 1, cmp1);
    int cnt = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        cnt++;
        if (dat[i] == dat[i + 1])continue;
        ++num;
        dat[num].x = dat[i].x;
        dat[num].y = dat[i].y;
        dat[num].z = dat[i].z;
        dat[num].cnt = cnt;
        cnt = 0;
    }
    cdq(1, num);
    for (int i = 1; i <= num; i++) {
        ans[dat[i].ans + dat[i].cnt - 1] += dat[i].cnt;
    }
    for (int i = 0; i < n; i++)printf("%d\n", ans[i]);


#ifndef ONLINE_JUDGE
    cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

动态逆序对

解法1：

对于动态逆序对，和三维偏序是一个问题。对于每一种删除操作，我们添加一个时间轴$t$,然后把下标当作一维度，就变成了三维，如样例 ：1 5 3 4 2 变成

1
2
3
1 2 3 4 5  下标
1 5 3 4 2  值
1 1 1 1 1  时间

每次修改，在$t$时间删除了值a,那么把他的时间变成对应修改时间。如样例删除顺序5 1 4 2，没有删除初始化为一个比较大的值，要在树状数组范围内。

1
2
3
1 2 3 4 5 
1 5 3 4 2
3 2 inf 4 5 删除时间

然后不难发现，每次删除一个数的贡献，就是原二维逆序对的基础上，加上一个约束条件 $t_i < t_j$ 。然后用总逆序对数量减去这个当前的时间的贡献就是答案。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
// luogu-judger-enable-o2
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid ((l + r) >> 1)
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define eb(x) emplace_back(x)
#define pb(x) emplace_back(x)
#define mem(a, b) memset(a, b, sizeof(a));

const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;

#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

//typedef __int128 LLL;

template<typename T>
void read(T &w) {//读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))
        w = w * 10 + (c & 15);
}

template<typename T>
void output(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    int ss[55], sp = 0;
    do
        ss[++sp] = x % 10;
    while (x /= 10);
    while (sp)
        putchar(48 + ss[sp--]);
}

struct node {
    int x, y, z;
} dat[maxn];

bool cmp1(node &o1, node &o2) {
    return o1.x == o2.x ? (o1.y == o2.y ? o1.z < o2.z : o1.y < o2.y) : o1.x > o2.x;
}

bool cmp2(node &o1, node &o2) {
    return (o1.y == o2.y ? o1.z < o2.z : o1.y < o2.y);
}

bool cmp3(node &o1, node &o2) {
    return o1.y > o2.y;
}

int a[maxn];
vector<int> v;
LL bit[maxn + 1], n;

LL sum(int i) {
    LL s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, LL x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

LL ans[maxn];

void cdq(int l, int r) {
    if (r == l)return;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(dat + l, dat + mid + 1, cmp2);
    sort(dat + mid + 1, dat + r + 1, cmp2);
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (dat[i].y < dat[j].y) {
            add(dat[i].z, 1);
            i++;
        } else {
            ans[dat[j].z] += sum(dat[j].z);
            j++;
        }
    }
    while (i <= mid) {
        add(dat[i].z, 1);
        i++;
    }
    while (j <= r) {
        ans[dat[j].z] += sum(dat[j].z);
        j++;
    }
    for (i = l; i <= mid; i++)add(dat[i].z, -1);


    i = l;
    j = mid + 1;
    sort(dat + l, dat + mid + 1, cmp3);
    sort(dat + mid + 1, dat + r + 1, cmp3);
    while (i <= mid && j <= r) {
        if (dat[i].y > dat[j].y) {
            ans[dat[i].z] += sum(dat[i].z);
//            add(dat[i].z, 1);
            i++;
        } else {
//            ans[dat[j].z] += sum(dat[j].z);
            add(dat[j].z, 1);
            j++;
        }
    }
    while (j <= r) {
//        ans[dat[j].z] += sum(dat[j].z);
        add(dat[j].z, 1);
        j++;
    }
    while (i <= mid) {
        ans[dat[i].z] += sum(dat[i].z);
//        add(dat[i].z, 1);
        i++;
    }

    for (j = mid + 1; j <= r; j++)add(dat[j].z, -1);
}

int main() {
    f();
    int m;
    read(n);
    read(m);
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        dat[i].x = i;
        read(dat[i].y);
//        res += sum(dat[i].y);
//        add(dat[i].y, 1);
        a[i] = 1;
    }
//    mem(bit, 0);
    for (int j = 0; j < m; ++j) {
        int x;
        read(x);
        a[x] = m - j + 1;
    }
    for (int i = 1; i <= n; ++i) {
        dat[i].z = a[dat[i].y];
    }
    sort(dat + 1, dat + n + 1, cmp1);
    for (int i = 1; i <= n; i++) {
//        dat[i].x = i;
//        read(dat[i].y);
        res += sum(dat[i].y);
        add(dat[i].y, 1);
//        a[i] = 1;
    }
    mem(bit, 0);
    cdq(1, n);
    for (int i = 0; i < m; i++) {
        printf("%lld\n", res);
        res -= ans[m + 1 - i];
    }
#ifndef ONLINE_JUDGE
    cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

解法2

原本我们这个写法是直接标记修改时间，这次我们变成添加一个相反的值。在原有的节点上，我们添加一个值，记录个数，删除久相当于添加一个个数为-1的节点。
例子就变成了

1
2
3
4
1  1 2  2 3   4  4 5  5 
1  1 5  5 3   4  4 2  2
1  3 1  2 inf 1  4 1  5 删除时间
1 -1 1 -1 1   1 -1 1 -1 个数

然后算贡献就可以直接算贡献了，很显然这种写法多了一个常数？那么为什么也要贴出来呢？，因为这个写法添加和删除都可以直接在上面做修改，添加就相当于加了一个个数为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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
// luogu-judger-enable-o2
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid ((l + r) >> 1)
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define eb(x) emplace_back(x)
#define pb(x) emplace_back(x)
#define mem(a, b) memset(a, b, sizeof(a));

const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;

#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

//typedef __int128 LLL;

template<typename T>
void read(T &w) {//读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))
        w = w * 10 + (c & 15);
}

template<typename T>
void output(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    int ss[55], sp = 0;
    do
        ss[++sp] = x % 10;
    while (x /= 10);
    while (sp)
        putchar(48 + ss[sp--]);
}

struct node {
    int x, y, z, cnt;
} dat[maxn];

bool cmp1(node &o1, node &o2) {
    if (o1.x == o2.x)return o1.y == o2.y ? o1.z > o2.z : o1.y < o2.y;
    return o1.x < o2.x;
}

bool cmp2(node &o1, node &o2) {
    return o1.y == o2.y ? o1.z > o2.z : o1.y > o2.y;
}

bool cmp3(node &o1, node &o2) {
    return o1.y == o2.y ? o1.z < o2.z : o1.y < o2.y;
}

int pos[maxn];

int bit[maxn];
int n, m;

LL sum2(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x) {
    while (i <= m + 1) {
        bit[i] += x;
        i += i & -i;
    }
}

LL ans[maxn];

void cdq(int l, int r) {
    if (r == l)return;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(dat + l, dat + mid + 1, cmp2);
    sort(dat + mid + 1, dat + r + 1, cmp2);
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (dat[i].y >= dat[j].y) {
            add(dat[i].z, dat[i].cnt);
            i++;
        } else {
            ans[dat[j].z] += sum2(dat[j].z) * dat[j].cnt;
            j++;
        }
    }
    while (i <= mid) {
        add(dat[i].z, dat[i].cnt);
        i++;
    }
    while (j <= r) {
        ans[dat[j].z] += sum2(dat[j].z) * dat[j].cnt;
        j++;
    }
    for (i = l; i <= mid; i++)add(dat[i].z, -dat[i].cnt);

    sort(dat + l, dat + mid + 1, cmp3);
    sort(dat + mid + 1, dat + r + 1, cmp3);

    i = l;
    j = mid + 1;
    while (i <= mid && j <= r) {
        if (dat[i].y > dat[j].y) {
            add(dat[j].z, dat[j].cnt);
            j++;
        } else {
//            if (dat[i].z == 2) {
//                bug;
//            }
            ans[dat[i].z] += sum2(dat[i].z) * dat[i].cnt;
            i++;
        }
    }

    while (i <= mid) {
//        if (dat[i].z == 2) {
//            bug;
//        }
        ans[dat[i].z] += sum2(dat[i].z) * dat[i].cnt;
        i++;
    }
    while (j <= r) {
        add(dat[j].z, dat[j].cnt);
        j++;
    }
    for (i = mid + 1; i <= r; i++)add(dat[i].z, -dat[i].cnt);
}

int main() {
    f();
    read(n);
    read(m);
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        read(dat[i].y);
        dat[i].x = i;
        pos[dat[i].y] = i;
        dat[i].cnt = 1;
        dat[i].z = 1;
    }
    for (int i = 1; i <= m; i++) {
        int x;
        read(x);
        dat[i + n].x = pos[x];
        dat[i + n].y = dat[pos[x]].y;
        dat[i + n].z = i + 1;
        dat[i + n].cnt = -1;
    }
    sort(dat + 1, dat + n + m + 1, cmp1);
    cdq(1, n + m);
    res = ans[1] / 2;
    for (int i = 2; i <= m + 1; i++) {
        printf("%lld\n", res);
        res += ans[i];
//        debug(ans[i]);
    }
#ifndef ONLINE_JUDGE
    cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

我校那题做练习，如果失效了就别做了，想试试可以留言。

启发式分治

恕我直言，不说话
分治很容易出现一种情况，你需要找的mid不是刚好在一半的位置，。。然后你就往离边界近的方向枚举。然后确定另一半的临界值。这个队友告诉我是$O(nlog(n))$但是我不确定。
例题，可以去我的启发式分治题标签里面找