分治算法综合(一)

分治算法中有一些值得探讨的高级专题
比如
$\textbf{CDQ分治,树上分治,整体分治}$
$\textbf{其中树上分治又被分为点分治,边分治,动态树分治}$
从这篇博文开始陆续对这些内容做一个补充

点分治

POJ1741

POJ1741
POJ1741
POJ1741

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

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, k;

// == Graph definition ==
int M = 0;
class Edge {
public:
int to, weight;
Edge *next;
Edge() {}
Edge(int to, int w) : to(to), weight(w) {
next = NULL;
}
} edges[maxn << 1], *head[maxn];

void initG() {
M = 0;
memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
edges[++M] = Edge(v, w);
edges[M].next = head[u];
head[u] = &edges[M];
}
// == Graph finished ==

// == find gravity and get root ==
int sz[maxn];
int sn = n;
int vis[maxn];
int root = 0;
void getRoot(int x, int pa, int& res) {
sz[x] = 1;
int maxpart = 0;
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;
if(vis[y] || y == pa) continue;

getRoot(y, x, res);
sz[x] += sz[y];
maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);
if(maxpart < res) {
res = maxpart;
root = x;
}
}
// == get root finished ==

// == getDep ==
int dep[maxn];

void getDep(int x, int pa, vector<int>& vec) {
vec.push_back(dep[x]);
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;
if(y == pa || vis[y]) continue;

dep[y] = dep[x] + w;
getDep(y, x, vec);
}
}
// == getDep finished ==

// == cal(p) ==
inline int cal(int x) {
vector<int> vec;
getDep(x, 0, vec);
sort(vec.begin(), vec.end());

int sum = 0, i = 0, j = vec.size() - 1;
while (i < j) {
if(vec[i] + vec[j] <= k) sum += j - i, i++;
else j--;
}
return sum;
}
// == cal(p) finished ==

// == work ==
void work(int x, int& ans) {
dep[x] = 0;
vis[x] = 1;
ans += cal(x);

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;
if(vis[y]) continue;

dep[y] = dep[x] + w;
ans -= cal(y);

sn = sz[y];
root = 0;
int res = inf;
getRoot(y, 0, res);

work(root, ans);
}
}
// == work finished ==

void init() {
//
Set(sz, 0);
Set(vis, 0);
sn = n;
root = 0;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &k) == 2 && n) {
initG();
init();

// input data
_for(i, 1, n) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
add(x, y, w);
add(y, x, w);
}
// input finished

int res = inf;
getRoot(1, 0, res);
int ans = 0;
work(root, ans);
printf("%d\n", ans);
}
}

点分治树状数组统计

$root \leftarrow getRoot(x)$
$\text{find }\textbf{gravity}$

$\textbf{algorithm: } solve(x\leftarrow \text{gravity})$
$\textbf{i) } x \text{ is the root, let } dep(x) = 0$
$\textbf{ii) } getDep(x \ \cup \ subTree)$
$\quad \quad \rightarrow \textbf{cal}(x)$
$\textbf{iii) for } \forall (x, y) \in [s_1, s_2, \cdots, s_k], s_i \text{ is subTree}$
$\quad \quad \quad sn = \text{size}(y)$
$\quad \quad \quad root \leftarrow getRoot(y), solve(root)$

$\textbf{algorithm: cal}(x)$

$\text{fwick}.add(dep(x), 1)$

$\textbf{for } \forall e(x, y) \in [S_i]$
$\quad \quad dep(y)=dep(x)+w(x, y)$
$\quad \quad getDep(y \ \cup \ S_i) \xrightarrow{dep} vec[\cdots]$

$\quad \quad \textbf{for }\forall(d:vec)$
$\quad \quad \textbf{i) } \text{fwick}.ask(K-d) \text{ count how many: } $
$\quad \quad \quad(S_j | S_j \neq S_i)+(d \in S_i) \leqslant K$
$\quad \quad \textbf{ii) then }\text{fwick}.add(d \in S_i, 1)$

$\text{reset fenwick}$
$\textbf{for }\forall (d:vec)$
$\quad \quad \text{fwick}.add(d, -1)$
$\text{fwick}.add(dep(x), -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
190
191
192
193
194
195
196
197

const int maxn = 1e5 + 10;
const int MAXN = maxn << 5;
const int inf = 0x3f3f3f3f;
int N, K;

// == Fenwick ==
class Fwick {
public:
vector<int> C;
int n;

void resize(int n) {
this->n = n;
C.resize(n);
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int ask(int x) {
x++;
int ans = 0;
for(; x > 0; x -= lowbit(x)) ans += C[x];
return ans;
}

void add(int x, int d) {
x++;
for(; x <= K + 10; x += lowbit(x)) C[x] += d;
}

int find(int l, int r, int val) {
while (l < r) {
int mid = (l + r) >> 1;
if(ask(mid) < val) l = mid + 1;
else r = mid;
}
return l;
}
} fwick;
// == Fenwick finished ==

// == Graph definition ==
int m = 0;

class Edge {
public:
int to, weight;
Edge *next;

Edge() {}
Edge(int to, int w) : to(to), weight(w) {
next = NULL;
}
} edges[maxn << 1], *head[maxn];

void add(int u, int v, int w) {
edges[++m] = Edge(v, w);
edges[m].next = head[u];
head[u] = &edges[m];
}

void initG() {
m = 0;
memset(head, 0, sizeof(head));
}
// == Graph finished ==

int sz[maxn];
int dep[maxn];
int vis[maxn];
int sn = N;
int root = 0;

// == get gravity as root ==
void getRoot(int x, int pa, int &res) {
sz[x] = 1;
int maxpart = 0;
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
if(vis[y] || y == pa) continue;

getRoot(y, x, res);
sz[x] += sz[y];
maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);
if(maxpart < res) {
res = maxpart;
root = x;
}
}
// == get root finished ==

// == get dep and calculate ==
void getDep(int x, int pa, vector<int> &vec) {
vec.push_back(dep[x]);
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;

if(vis[y] || y == pa) continue;
dep[y] = dep[x] + w;

if(dep[y] <= K) getDep(y, x, vec);
}
}

queue<int> buf;
inline void cal(int x, int &ans) {
fwick.add(dep[x], 1);

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;
if(vis[y]) continue;

dep[y] = dep[x] + w;
vector<int> vec;
getDep(y, x, vec);

_for(i, 0, vec.size()) if(K >= vec[i]) {
ans += fwick.ask(K - vec[i]);
}

_for(i, 0, vec.size()) {
fwick.add(vec[i], 1);
buf.push(vec[i]);
}
}

while (buf.size()) {
fwick.add(buf.front(), -1);
buf.pop();
}
fwick.add(dep[x], -1);
}
// == get dep finsihed ==

// == solve ==
void solve(int x, int &ans) {
dep[x] = 0;
vis[x] = 1;
cal(x, ans);

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;

if(vis[y]) continue;

sn = sz[y];
root = 0;
int res = inf;
getRoot(y, -1, res);

solve(root, ans);
}
}
// == solve finished ==

void init() {
Set(sz, 0);
Set(dep, 0);
Set(vis, 0);
sn = N;
root = 0;

fwick.resize(MAXN);
fwick.clear();
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &N, &K) == 2 && N) {
init();
initG();

// get data
_for(i, 1, N) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
// data finished

int res = inf;
getRoot(1, -1, res);

int ans = 0;
solve(root, ans);
printf("%d\n", ans);
}
}

点分治例子

Acwing264

$\textbf{algorithm}$
$\textbf{i) solve}(x, \text{ans})$
$\quad \quad \text{dep}(x) = 0, \text{vis}(x) = 1$
$\quad \quad \textbf{cal}(x, ans)$
$\quad \quad \textbf{for } \forall y \in son(x)$
$\quad \quad \quad root \leftarrow getRoot(), \textbf{solve}(root, ans)$

$\textbf{ii) cal}(x, y), \text{难点在于cal的计算}$

Acwing264

$\textbf{用 vec1}[\cdots] \textbf{ 维护 D}[\cdots], \textbf{vec2}[\cdots] \textbf{ 维护 dep}[\cdots]$

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
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int N, K;

// == Graph definition ==
int m = 0;

class Edge {
public:
int to, weight;
Edge *next;

Edge() {}
Edge(int to, int w) : to(to), weight(w) {
next = NULL;
}
} edges[maxn << 1], *head[maxn];

void initG() {
m = 0;
memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
edges[++m] = Edge(v, w);
edges[m].next = head[u];
head[u] = &edges[m];
}
// == Graph finished ==

// == get root ==
int root = 0;
int sn = N;
int sz[maxn];
int vis[maxn];

void getRoot(int x, int pa, int &res) {
sz[x] = 1;

int maxpart = 0;
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
if(vis[y] || y == pa) continue;

getRoot(y, x, res);

sz[x] += sz[y];
maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);

if(maxpart < res) {
res = maxpart;
root = x;
}
}
// == get root finished ==

// == solve ==
int dep[maxn];
int D[maxn];
int dp[maxn];

void dfs(int x, int pa, vector<int> &vec1, vector<int> &vec2) {
vec1.push_back(D[x]);
vec2.push_back(dep[x]);
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;

if(vis[y] || y == pa) continue;

dep[y] = dep[x] + 1;
D[y] = D[x] + w;

if(D[y] <= 1e6) dfs(y, x, vec1, vec2);
}
}

queue<int> que;
void cal(int x, int &ans) {
for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;

if(vis[y]) continue;

vector<int> vec1, vec2;
dep[y] = dep[x] + 1;
D[y] = D[x] + w;
dfs(y, x, vec1, vec2);

_for(i, 0, vec1.size()) {
if(K >= vec1[i]) ans = min(ans, dp[K - vec1[i]] + vec2[i]);
}

_for(i, 0, vec1.size()) {
que.push(vec1[i]);
dp[vec1[i]] = min(dp[vec1[i]], vec2[i]);
}
}
while (que.size()) {
dp[que.front()] = inf;
que.pop();
}
}

void solve(int x, int &ans) {
vis[x] = 1;
dep[x] = 0;
D[x] = 0;
dp[0] = 0;

cal(x, ans);

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->weight;

if(vis[y]) continue;

sn = sz[y];
root = 0;
int res = inf;
getRoot(y, x, res);

solve(root, ans);
}
}
// == solve finished ==

void init() {
root = 0;
sn = N;
Set(sz, 0);
Set(vis, 0);
Set(dep, 0);
Set(D, 0);
Set(dp, inf);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &N, &K);
initG();
init();

_for(i, 1, N) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u++; v++;
add(u, v, w);
add(v, u, w);
}

// then solve the problem
int res = inf;
getRoot(1, -1, res);
int ans = inf;
solve(root, ans);

if(ans == inf) printf("-1\n");
else printf("%d\n", ans);
}

一些算法技巧

$\textbf{algorithm 差分}$

$A[…]=A_1,A_2,A_3, \cdots ,A_n$
$B_i = A_i - A_{i-1}, \ B_1 = A_1$
$B就是A的差分序列$

$\textbf{性质1}$

$\textbf{性质2}$
$A[l, r] \xleftarrow{+C}$
$给区间 A[l, r] 的元素都加上 C$

$\Leftrightarrow B_{r+1} - C, B_{l} + C$

Acwing100

$\textbf{algorithm, solve }(B_i, B_j) , i < j$
$\text{目标是把 } B_2, B_3\cdots, B_n 全部变成0$

$\textbf{i) } 2\leqslant i < j \leqslant n, \text{ 能够处理 } B[2\cdots n] \text{ 中的 } 2 \text{ 个数 } B_i, B_j$
$\quad \text{改变的是区间 } A[i, \cdots, j-1]$
$\quad \text{在一正一负的时候尽可能用这种操作}$

$\textbf{ii) } i = 1, 2 \leqslant j \leqslant n$
$\quad \text{改变的是} A[\cdots] 的前缀$

$\textbf{iii) } 2 \leqslant i \leqslant n, j = n + 1$
$\quad \text{改变的是} A[\cdots] 的后缀$

$\textbf{iv) } i = 1, j = n + 1$
$\quad \text{改变了整个 }A 序列,无意义$

$\textbf{algorithm}$
$\textbf{i) do } \text{type i) , when } B_i \cdot B_j <0$
$\textbf{ii) } \text{other, do type ii) or iii)}$
$\quad \text{ example, remain }\textbf{r unpaired}$
$\quad \rightarrow [\text{ii)}, \text{iii)}] = (0, r), (1, r), \cdots, (r, 0)$
$\quad \rightarrow tot =r+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
const int maxn = 1e5 + 10;
int A[maxn], B[maxn];
int n;

void init() {
Set(B, 0);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);
init();

_rep(i, 1, n) scanf("%d", &A[i]);

B[1] = 1;
_rep(i, 2, n) B[i] = A[i] - A[i - 1];

ll s1 = 0, s2 = 0;
_rep(i, 2, n) {
if(B[i] > 0) s1 += B[i];
else s2 -= B[i];
}

ll ans = min(s1, s2) + abs(s1 - s2);
cout << ans << endl;

ll ans2 = abs(s1 - s2) + 1;
cout << ans2 << endl;
}

树状数组维护差分序列

POJ3468

$[l, r] \xleftarrow{+d}$
$B_i = A_i - A_{i - 1}$

$\textbf{algorithm}$
$\textbf{i) } \text{fwick[0]} \leftarrow \sum_{i = 1}^{x} B_i, \quad \text{fwick[1]} \leftarrow \sum_{i = 1}^{x} i B_i$
$\textbf{ii) change: } [l, r]$
$\quad \quad \text{fwick[0]}.add(r+1, -d), \quad \text{fwick[0]}.add(l, d)$
$\quad \quad \text{fwick[1]}.add(r+1, -(r+1)d), \quad \text{fwick[1]}.add(l, ld)$
$\textbf{ii) ask: } [l, r]$
$\quad \quad S(r) = (\text{fwick}[0].ask(r)) \times (r+1) - \text{fwick[1]}(r)$
$\quad \quad S(l -1) = (\text{fwick}[0].ask(l - 1)) \times (l) - \text{fwick[1]}(l - 1)$
$\quad \quad \textbf{ans} = S(r) - S(l - 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

const int maxn = 100000 + 10;
int n, m;
ll A[maxn];

// == fenwick definition ==
class Fwick {
public:
vector<ll> C[2];
int n;

void resize(int n) {
this->n = n;
_for(i, 0, 2) C[i].resize(n + 1);
}

void clear() {
_for(i, 0, 2) fill(C[i].begin(), C[i].end(), 0ll);
}

void add(int k, int x, ll d) {
int i = x;
for(; i <= n; i += lowbit(i)) C[k][i] += 1ll * d;
}

ll ask(int k, int x) {
ll ans = 0;
for(int i = x; i; i -= lowbit(i)) ans += C[k][i];
return ans;
}

} fwick;
// == fenwick finsihed ==

ll prefix(int x) {
return fwick.ask(0, x) * (x + 1) - fwick.ask(1, x);
}

void init() {
fwick.resize(maxn);
fwick.clear();
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
init();

_rep(i, 1, n) {
scanf("%lld", &A[i]);
fwick.add(0, i, A[i] - A[i - 1]);
fwick.add(1, i, i * (A[i] - A[i - 1]));
}

// then solve
while (m--) {
char cmd[2];
scanf("%s", cmd);
if(cmd[0] == 'C') {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);

fwick.add(0, r + 1, -1ll * d);
fwick.add(0, l, 1ll * d);

fwick.add(1, r + 1, -1ll * d * (r + 1));
fwick.add(1, l, 1ll * d * l);
}
else {
int l, r;
scanf("%d%d", &l, &r);

ll ans = prefix(r) - prefix(l - 1);
printf("%lld\n", ans);
}
}
}

树状数组求逆序对

$\textbf{algorithm: A}[\cdots]$
$\textbf{for } \forall i \in [1, n]$
$\quad \textbf{check } [1, 2, \cdots, i] \rightarrow \textbf{fwick}[\cdots]$
$\quad \textbf{fwick}.add(A[i], 1)$

$\quad \textbf{fwick}.sum(A[i]) \rightarrow (\text{how many} \leqslant A[i]) \in [1, \cdots, i]$

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
class Solution {
public:
int inversePairs(vector<int>& nums) {
int n = nums.size();
#define lowbit(x) (x & (-x))
typedef long long ll;
int b[n + 1], a[n + 1];

class Fwick {
public:
vector<ll> C;
int n;
void resize(int n) {
this->n = n;
C.resize(n + 1);
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int sum(int x) {
int ans = 0;
for(; x > 0; x -= lowbit(x)) ans += C[x];
return ans;
}

int add(int x, int d) {
for(; x <= n; x += lowbit(x)) C[x] += d;
}
} fwick;


for(int i = 1; i <= (int)nums.size(); i++) {
a[i] = b[i] = nums[i - 1];
}

sort(b + 1, b + 1 + n);
int tot = unique(b + 1, b + 1 + n) - b - 1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;

fwick.resize(tot + 1);
fwick.clear();

int ans = 0;
for(int i = 1; i <= n; i++) {
fwick.add(a[i], 1);
ans += i - fwick.sum(a[i]);
}
return ans;
}
};