CF643D - Bearish Fanpages

被浏览

作为一道英文题,我们先解释一下题意。

题面有点长就不解释了,大家自己翻译吧。

首先有一个 Simple 的想法,直接维护啊,变的节点又不多,修改不是 $O(1)$ 的吗?

然后发现错了。

我们发现因为 $D_i$ 变了,$E_i$ 也会变!

考虑遍历所有变更过的节点,此时复杂度上界是 $O(n^2)$,比如菊花树就能随便卡。

但我们发现实际上变更的内容很少,考虑将信息分开维护。

我们将题目中的 $A_i$ 看作 $i$ 的父亲,将 $A_j=i$ 的点都看作 $i$ 的儿子。

对于一个节点,维护 $A_i$,$E_i$,$g_i$,$f_i$。

$A_i$,$E_i$ 定义同题意,$f_i$ 表示它自己和它的儿子对自己的贡献,$g_i$ 表示它儿子中所有 $f_i$ 所组成的集合。

对于全局则维护一个 $ans$,其中元素为 $E_i+(g_i)_{max}$ 和 $E_i+(g_i)_{min}$,这样就能覆盖所有的情况了。

不难发现 $C_i=f_i+E_{A_i}$。

这么分开的好处就是对于操作一,我们发现只会影响到 $A_x$,$A_{A_x}$,$A_{A_{A_x}}$,$y$,$A_y$,$A_{A_y}$ 中维护的信息,其中的操作复杂度均为 $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
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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
typedef long long LL;
inline char _gc() {
static char buf[1 << 14], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 14, stdin), p1 == p2) ? EOF : *p1++;
}
#define gc c = _gc()
LL read() {
LL x = 0, f = 1;
char gc;
for (; !isdigit(c); gc)
if (c == '-') f = -1;
for (; isdigit(c); gc) x = x * 10 + c - '0';
return x * f;
}
#undef gc
const int N = 1e5 + 5;
LL A[N], B[N], D[N], E[N], f[N];
int tmp[10];
multiset<LL> g[N], ans;
// 可能会有重复的,开multiset
int main() {
int n = read(), q = read();
for (int i = 1; i <= n; i++) B[i] = read(), D[i] = 2;
for (int i = 1; i <= n; i++) A[i] = read(), D[A[i]]++;
for (int i = 1; i <= n; i++) E[i] = B[i] / D[i];
for (int i = 1; i <= n; i++) f[A[i]] += E[i];
for (int i = 1; i <= n; i++) f[i] += E[i] + B[i] % D[i];
for (int i = 1; i <= n; i++) g[A[i]].insert(f[i]);
for (int i = 1; i <= n; i++)
if (g[i].size()) {
ans.insert(E[i] + *g[i].begin());
ans.insert(E[i] + *(--g[i].end()));
}
while (q--) {
int opt = read();
if (opt == 1) {
int x = read(), y = read();
if (A[x] == y) continue;
// 注意此处,不然会使D[i]出问题
tmp[0] = x, tmp[1] = A[x], tmp[2] = A[A[x]], tmp[3] = A[A[A[x]]];
tmp[4] = y, tmp[5] = A[y], tmp[6] = A[A[y]];
sort(tmp, tmp + 7);
for (int i = 0; i < 7; i++) {
if (tmp[i] == tmp[i + 1]) continue;
// 注意给tmp去重,不去重的话会导致多删除信息
int x = tmp[i];
if (g[x].size()) {
ans.erase(ans.find(E[x] + *g[x].begin()));
ans.erase(ans.find(E[x] + *(--g[x].end())));
}
}
// A[x]的E、f变了,A[A[x]]的f变了
// 维护f
// A[A[x]]
g[A[A[A[x]]]].erase(g[A[A[A[x]]]].find(f[A[A[x]]]));
f[A[A[x]]] = f[A[A[x]]] - E[A[x]] + B[A[x]] / (D[A[x]] - 1);
g[A[A[A[x]]]].insert(f[A[A[x]]]);
// A[x]
g[A[A[x]]].erase(g[A[A[x]]].find(f[A[x]]));
f[A[x]] = f[A[x]] - E[x] - (E[A[x]] + B[A[x]] % D[A[x]]) +
B[A[x]] / (D[A[x]] - 1) + B[A[x]] % (D[A[x]] - 1);
g[A[A[x]]].insert(f[A[x]]);
// 把x接到y上去
g[A[x]].erase(g[A[x]].find(f[x]));
g[y].insert(f[x]);
// y的E、f变了,A[y]的f变了
// 维护f
// A[y]
g[A[A[y]]].erase(g[A[A[y]]].find(f[A[y]]));
f[A[y]] = f[A[y]] - E[y] + B[y] / (D[y] + 1);
g[A[A[y]]].insert(f[A[y]]);
// y
g[A[y]].erase(g[A[y]].find(f[y]));
f[y] = f[y] - (E[y] + B[y] % D[y]) + B[y] / (D[y] + 1) +
B[y] % (D[y] + 1) + E[x];
g[A[y]].insert(f[y]);
// 维护E
D[A[x]]--, D[y]++;
E[A[x]] = B[A[x]] / D[A[x]], E[y] = B[y] / D[y];
for (int i = 0; i < 7; i++) {
int x = tmp[i];
if (tmp[i] == tmp[i + 1]) continue;
if (g[x].size()) {
ans.insert(E[x] + *g[x].begin());
ans.insert(E[x] + *(--g[x].end()));
}
}
A[x] = y;
}
if (opt == 2) {
int x = read();
printf("%lld\n", f[x] + E[A[x]]);
}
if (opt == 3) printf("%lld %lld\n", *ans.begin(), *(--ans.end()));
}
}