不会暴力, 分块好难.
$n$ 个点 $m$ 条边的无向图, $q$ 次询问, 每次修改一个点的信息, 或者查询一个点的所有相邻点的信息和. 这样的东西还真没有什么数据结构好维护. 然后就有了图论分块这种优美的暴力, 均摊复杂度 $O(q\sqrt m)$.
图论分块的核心思想是, 将度数多的点和度数少的点分类, 度数少的点暴力, 度数多的点尝试维护答案.
将度数大于 $\sqrt{2m}$ 的点分成一类, 称为重点, 其他点分为一类, 称为轻点, 那么有:
- 一个轻点最多和 $\sqrt{2m}$ 个点相邻
- 一个重点最多和 $\sqrt{2m}$ 个重点相邻
然后构造一个有向的更新关系, 轻点向和他相邻的重点连有向边, 表示这个轻点被修改后, 需要维护重点的信息; 重点向和它相邻的重点连有向边, 表示这个重点被修改后, 需要维护和它相邻的重点的信息. 那么一次修改加上维护相邻重点, 复杂度是 $O(\sqrt{2m})$ 的. 查询如果是重点, 那么已经维护过了, 直接输出答案即可; 如果是轻点, 那么暴力去算和它相邻的点的信息和即可, 轻点度数不超过 $\sqrt{2m}$, 故一次查询的复杂度也是 $O(\sqrt{2m})$, 总复杂度 $O(q \sqrt{2m}) = O(q \sqrt m)$.
这个思想就是, 如果去维护答案, 修改信息复杂度很高, 如果去维护信息, 统计答案复杂度很高, 那么找一个"平衡点", 维护一些信息, 统计一些答案, 就可以均摊下来了(好像这就是莫队的思想, 咱也不懂, 咱也不敢问).
板题: HDU-4858
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
|
int T, n, m, deg[MAXN], S, q, a[MAXN], sum[MAXN];
VI G[MAXN], E[MAXN];
void init() {
for (int i = 1; i <= n; i++)
G[i].clear(), E[i].clear(),
deg[i] = a[i] = sum[i] = 0;
}
int query(int u) {
if (deg[u] > S)
return sum[u];
int res = 0;
for (int v : G[u])
res += a[v];
return res;
}
void update(int u, int d) {
a[u] += d;
for (int v : E[u])
sum[v] += d;
}
void build() {
for (int i = 1; i <= n; i++)
for (int v : G[i]) if (deg[v] > S)
E[i].push_back(v);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
deg[u]++, deg[v]++;
}
S = sqrt(2 * m);
build();
scanf("%d", &q);
while (q--) {
int op, u, d;
scanf("%d%d", &op, &u);
if (op)
printf("%d\n", query(u));
else {
scanf("%d", &d);
update(u, d);
}
}
}
return 0;
}
|
当然也可以维护周围点边权的信息和: HDU-4467
这道题就记录三种情况的答案. 重点记录一个 $sum(u, j)$ 表示颜色为 $j$ 的边的权值和. 修改如果是轻点, 那么遍历和它相邻的点, 如果是轻点, 那么直接更新最终答案; 如果是重点, 在更新答案的同时还需要维护 $sum$. 修改如果是重点, 由于已经维护了信息, 直接用 $sum$ 去更新答案即可.
你永远可以相信hdu评测机
这题有重边, 需要去重, 然后还要用邻接表, 否则T到起飞.
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
|
struct E {
int u, v;
LL w;
bool operator < (const E &E) const {
return u == E.u ? v == E.v ? w < E.w : v < E.v : u < E.u;
}
};
vector<E> edges0;
struct Edge {
int to, next;
LL w;
} edges[2][MAXN<<1];
int head[2][MAXN], mm[2];
void addEdge(int g, int u, int v, LL w) {
edges[g][++mm[g]] = {v, head[g][u], w};
head[g][u] = mm[g];
}
void addNet(int g, int u, int v, LL w) {
addEdge(g, u, v, w);
addEdge(g, v, u, w);
}
int n, m, c[MAXN], deg[MAXN], S, q;
LL ans[5], sum[MAXN][5];
int getAnsId(int a, int b) {
return a + b;
}
void init() {
edges0.clear();
mm[0] = mm[1] = 0;
ans[0] = ans[1] = ans[2] = 0;
for (int i = 1; i <= n; i++)
deg[i] = sum[i][0] = sum[i][1] = 0,
head[0][i] = head[1][i] = 0;
}
void build() {
for (int u = 1; u <= n; u++)
for (int i = head[0][u]; i; i = edges[0][i].next) {
Edge &e = edges[0][i];
if (deg[e.to] > S)
addEdge(1, u, e.to, e.w);
}
}
void update(int u) {
c[u] ^= 1;
for (int i = head[1][u]; i; i = edges[1][i].next) {
Edge &e = edges[1][i];
sum[e.to][c[u]] += e.w;
sum[e.to][c[u]^1] -= e.w;
}
if (deg[u] <= S) {
for (int i = head[0][u]; i; i = edges[0][i].next) {
Edge &e = edges[0][i];
ans[getAnsId(c[u], c[e.to])] += e.w;
ans[getAnsId(c[u]^1, c[e.to])] -= e.w;
}
}
else {
ans[getAnsId(c[u], 0)] += sum[u][0];
ans[getAnsId(c[u]^1, 0)] -= sum[u][0];
ans[getAnsId(c[u], 1)] += sum[u][1];
ans[getAnsId(c[u]^1, 1)] -= sum[u][1];
}
}
int main() {
int kase = 0;
while (scanf("%d%d", &n, &m) != EOF && ++kase) {
printf("Case %d:\n", kase);
init();
for (int i = 1; i <= n; i++)
scanf("%d", c+i);
for (int i = 1; i <= m; i++) {
int u, v;
LL w;
scanf("%d%d%lld", &u, &v, &w);
if (u > v)
swap(u, v);
edges0.push_back({u, v, w});
}
sort(edges0.begin(), edges0.end());
for (int i = 0, j; i < m; i = j) {
for (j = i + 1; j < m && edges0[i].u == edges0[j].u && edges0[i].v == edges0[j].v; j++)
edges0[i].w += edges0[j].w;
addNet(0, edges0[i].u, edges0[i].v, edges0[i].w);
deg[edges0[i].u]++, deg[edges0[i].v]++;
ans[getAnsId(c[edges0[i].u], c[edges0[i].v])] += edges0[i].w;
}
S = sqrt(m * 2);
build();
for (int u = 1; u <= n; u++)
for (int i = head[1][u]; i; i = edges[1][i].next) {
Edge &e = edges[1][i];
sum[e.to][c[u]] += e.w;
}
scanf("%d", &q);
while (q--) {
char str[10];
scanf("%s", str);
if (str[0] == 'A') {
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", ans[getAnsId(a, b)]);
}
else {
int u;
scanf("%d", &u);
update(u);
}
}
}
return 0;
}
|
还可以用数据结构维护重点的相邻点信息和, 比如 HDU-6756
写不动了, 咕咕咕.
第二天填坑, 还是写得动的^_^
这道题就是轻点暴力找mex, 重点需要用数据结构维护, 求mex. 这里有一个很神奇的操作, 对每个重点开一颗权值为它的度数+1的权值树状数组, $x$ 位为 $1$ 表示 $x-1$ 在它的周围出现过(树状数组下标从 $1$ 开始, 所以这里要整体平移一下), 并不需要管大于度数+1的数, 因为它不可能是mex, 等于度数的数其实也不用放进去, 因为前面填满就是0到度数-1, 填满了可以直接判, 如果出现等于度数的数, 那么前面一定没有填满. 假设 $mex = p$, 那么 $\forall x < p, presum(x) = x, \forall y \ge p, presum(y) < y$, 满足单调性, 可以二分. 这样查询一个重点的复杂度是 $O(\log m)$. 查询轻点就暴力, 复杂度 $O(\sqrt{2m}) = O(\sqrt m)$. 修改还是需要维护重点, 由于维护的是树状数组, 所以复杂度是 $O(\sqrt {2m} \log m) = O(\sqrt m \log m)$. 总复杂度 $O(q \sqrt m \log m)$
为方便这里把 cnt 放进了 bit 结构体内
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
|
struct BIT {
VI t, cnt;
int n;
void init(int _n) {
n = _n+1;
t.clear(), cnt.clear();
t.resize(n+1, 0), cnt.resize(n+1, 0);
}
/* 单点修改(加) */
void update(int pos, int x) {
for (int i = pos; i <= n; i += lowbit(i))
t[i] += x;
}
/* 查询前缀和 */
int presum(int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i))
res += t[i];
return res;
}
/* 查询区间[l, r]的和 */
int query(int l, int r) {
return presum(r) - presum(l-1);
}
void add(int x) {
if (++cnt[x] == 1)
update(x+1, 1);
}
void del(int x) {
if (--cnt[x] == 0)
update(x+1, -1);
}
int getMex() {
int l = 1, r = n, res = 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (presum(mid) < mid)
res = mid, r = mid - 1;
else
l = mid + 1;
}
return res-1;
}
} bit[MAXN];
int T, n, m, a[MAXN], deg[MAXN], S, ans[MAXN], idx, q;
VI G[MAXN], E[MAXN];
void init() {
for (int i = 1; i <= n; i++)
G[i].clear(), E[i].clear(),
deg[i] = 0;
}
void build() {
for (int u = 1; u <= n; u++)
for (int v : G[u]) if (deg[v] > S)
E[u].push_back(v);
}
void update(int u, int x) {
for (int v : E[u]) if (a[u] < deg[v])
bit[v].del(a[u]),
bit[v].add(x);
a[u] = x;
}
int tmp[MAXN];
int query(int u) {
if (deg[u] > S)
return bit[u].getMex();
else {
for (int i = 0; i <= deg[u]; i++)
tmp[i] = 0;
for (int v : G[u]) if (a[v] < deg[u])
tmp[a[v]]++;
for (int i = 0; i <= deg[u]; i++)
if (!tmp[i])
return i;
return deg[u];
}
}
int main() {
#ifdef GDB
freopen("X.in", "r", stdin);
freopen("X.out", "w", stdout);
#endif
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
deg[u]++, deg[v]++;
}
S = sqrt(2 * m);
build();
for (int u = 1; u <= n; u++) if (deg[u] > S)
bit[u].init(deg[u]);
for (int u = 1; u <= n; u++)
for (int v : E[u]) if (a[u] < deg[v])
bit[v].add(a[u]);
scanf("%d", &q);
while (q--) {
int op, u, x;
scanf("%d%d", &op, &u);
if (op == 1) {
scanf("%d", &x);
update(u, x);
}
else
printf("%d\n", query(u));
}
}
return 0;
}
|
图论分块 — AEMShana