CF643D - Bearish Fanpages

 OI / CodeForces
被浏览 次

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

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

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

然后发现错了。

我们发现因为 DiD_i 变了，EiE_i 也会变！

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

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

我们将题目中的 AiA_i 看作 ii 的父亲，将 Aj=iA_j=i 的点都看作 ii 的儿子。

对于一个节点，维护 AiA_i，EiE_i，gig_i，fif_i。

AiA_i，EiE_i 定义同题意，fif_i 表示它自己和它的儿子对自己的贡献，gig_i 表示它儿子中所有 fif_i 所组成的集合。

对于全局则维护一个 ansans，其中元素为 Ei+max⁡giE_i+\max\\{g_i\\} 和 Ei+min⁡giE_i+\min\\{g_i\\}，这样就能覆盖所有的情况了。

不难发现 Ci=fi+EAiC_i=f_i+E_{A_i}。

这么分开的好处就是对于操作一，我们发现只会影响到 AxA_x，AAxA_{A_x}，AAAxA_{A_{A_x}}，yy，AyA_y，AAyA_{A_y} 中维护的信息，其中的操作复杂度均为 lognlog_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()));
  }
}
 上一页