[EZOI][1208NOI模拟赛]Forest(multiset)

§ 1 题意

有一个点数为 $n$ 的有向图,每个点出度均为 $1$。

给出每个点的后继 $A_i$ 和点权 $B_i$,保证 $A_i \neq i$ 且 $A_{A_i} \neq i$。

记点 $i$ 的总度数为 $D_i$,并定义 $E_i = \lfloor \frac{B_i}{D_i} \rfloor$,稠密度 $C_i=B_i-D_i*E_i+\sum_{j=1}^{D_i}E_{P_j}$。

请实现一个稠密度分析仪,支持以下三种操作:

  • $1$ $i$ $j$ :把 $i$ 点的后继改为 $j$,即令 $A_i=j$,保证 $j \neq i$ 且 $A_j \neq i$。
  • $2​$ $i​$ :询问 $i​$ 点的稠密度 $C_i​$。
  • $3$ :询问所有节点中,$C_i$ 的最小值和最大值。

$3 \leq n \leq 10^5$,$1 \leq q \leq 10^5$,$1 \leq B_i \leq 10^{12}$,$1 \leq A_i \leq n$。

题目来源:Codeforces 643D - Bearish Fanpages


§ 2 分析

首先化简得 $C_i=B_i \% D_i+\sum_{j=1}^{D_i}E_{P_j}$。

考虑操作 $1$,将点 $i$ 的后继从 $A_i$ 改为 $j$,若 $A_i==j$ 则跳过,否则考虑改动所造成的影响:

  • $A_i$ 的度数减少 $1$,即 $D_{A_i}$ 减去 $1$,导致 $E_{A_i} = \lfloor \frac{B_{A_i}}{D_{A_i}} \rfloor$ 改变。
  • $j$ 的度数增加 $1$,即 $D_j$ 加上 $1$,导致 $E_j = \lfloor \frac{B_j}{D_j} \rfloor$ 改变。
  • 连边情况改变,即最后令 $A_i=j​$。

当某个 $E_i$ 改变时,$C_{i}$、$C_{A_i}$ 以及 $i$ 所有前驱 $j$ 的 $C_j$ 都要改变。

§ 2.1 弱化版

若没有 $3$ 操作,则我们考虑维护 $C’_i=C_i-E_{A_i}$,即不计后继贡献时的答案。

执行 $1$ $i$ $j$ 操作时,由于不计后继贡献, $C’_i$ 不会改变,重算 $E_{A_i}$ 和 $E_j$,更新 $C’_{A_i}$、$C’_{A_{A_i}}$、$C’_j$ 和 $C’_{A_j}$。

执行 $2$ $i$ 操作时,直接输出 $C’_i+E_{A_i}$ 即可。

总体可在 $O(n)$ 时间内解决。

§ 2.2 维护极值

考虑 $3$ 操作,我们可以对每个节点 $i$ 用 multiset 维护其前驱 $C’_i$ 的极值,然后取每个 multiset 中的极值再放入 multiset 中维护,即可在 $O(n\log n)$ 时间内解决本题。

注意每次更新 $C’_i$ 时,先在维护总体极值的 multiset 中删除,然后在父节点的 multiset 中删除,修改 $C’_i$ 后再在父节点的 multiset 中插入,最后在总体极值的 multiset 中插入即可。


§ 3 代码

注:C[i] 表示本文中的 $C’_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
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;

template <typename T> inline void getint(T &num){
register int ch, neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

int n, q, A[100005], D[100005];
ll B[100005], E[100005], C[100005];
multiset<ll> s[100005], maxs, mins;

inline void ins(const int &u){
if(s[u].empty()) return;
maxs.insert(*s[u].rbegin() + E[u]);
mins.insert(*s[u].begin() + E[u]);
}

inline void del(const int &u){
if(s[u].empty()) return;
maxs.erase(maxs.find(*s[u].rbegin() + E[u]));
mins.erase(mins.find(*s[u].begin() + E[u]));
}

int main(){
getint(n), getint(q);
for(register int i = 1; i <= n; i++) getint(B[i]), D[i] = 2;
for(register int i = 1; i <= n; i++) getint(A[i]), D[A[i]]++;
for(register int i = 1; i <= n; i++) E[i] = B[i] / D[i], C[i] = B[i] % D[i] + E[i];
for(register int i = 1; i <= n; i++) C[A[i]] += E[i];
for(register int i = 1; i <= n; i++) s[A[i]].insert(C[i]);
for(register int i = 1; i <= n; i++) ins(i);
while(q--){
int opt, u, v; getint(opt);
if(opt == 1){
getint(u), getint(v);
if(A[u] == v) continue;

int p = A[u], q = A[p], r = A[q];
del(p), s[p].erase(s[p].find(C[u]));
del(q), s[q].erase(s[q].find(C[p]));
del(r), s[r].erase(s[r].find(C[q]));

C[p] -= B[p] % D[p] + E[u] + E[p], C[q] -= E[p];
E[p] = B[p] / --D[p];
C[p] += B[p] % D[p] + E[p], C[q] += E[p];

ins(p);
s[q].insert(C[p]), ins(q);
s[r].insert(C[q]), ins(r);

p = A[u] = v, q = A[p], r = A[q];
del(p);
del(q), s[q].erase(s[q].find(C[p]));
del(r), s[r].erase(s[r].find(C[q]));

C[p] -= B[p] % D[p] + E[p], C[q] -= E[p];
E[p] = B[p] / ++D[p];
C[p] += B[p] % D[p] + E[u] + E[p], C[q] += E[p];

s[p].insert(C[u]), ins(p);
s[q].insert(C[p]), ins(q);
s[r].insert(C[q]), ins(r);
}
else if(opt == 2) getint(u), printf("%lld\n", C[u] + E[A[u]]);
else if(opt == 3) printf("%lld %lld\n", *mins.begin(), *maxs.rbegin());
}
return 0;
}