题解：P15762 [JAG 2025 Summer Camp #1] Inside Yamanote
manboo
·
·
题解
下文所有变量的角标都对 n 取模，如 i + 1 代表 (i + 1) \bmod n。
设首都为 pos，每个点到首都的距离为 d_i，若满足 |d_{i + 1} - d_i| \le l_i 且 d_i \ge 0 且存在 d_i = 0，则必然存在一种合法的建边方案。后两个条件分别代表距离非负、存在首都；第一个条件是因为可以让 pos 向 i(i \ne pos) 连边，边权为 d_i，当且仅当满足 |d_{i + 1} - d_i| \le l_i 时，pos, i, i + 1 在几何平面上构成三角形（或三点共线），则 pos 到 i 的距离为 d_i。
最后要求的声誉，是所有 d_{X_i} - d_{Y_i} 的总和。考虑每个 d_i 的贡献，必然是一个系数乘上 d_i，设其为 s_i。那么每次让 s_{X_i} 加一，s_{Y_i} 减一即可。由于每次都加一个、减一个，必然有 \sum\limits_{i = 0}^{n - 1} s_i = 0。
则答案为：\sum\limits_{i = 0}^{n - 1} s_i \times d_i。
然后就是人类智慧了。发现对于一种只满足 |d_{i + 1} - d_i| \le l_i 的 d_i 方案，必然可以令其变成合法方案（即变得同时满足之前所说的三个条件）。因为令 c = -\min d_i，令全体 d_i 加上 c，则此时最小的 d_i 变成 0，其余 d_i 同样 \ge 0，同时仍然满足 |d_{i + 1} - d_i| \le l_i（因为都加上同一个值，差还是不变）。
于是可以抛开首都，d_i 方案只需要满足 |d_{i + 1} - d_i| \le l_i，求 \sum\limits_{i = 0}^{n - 1} s_i \times d_i 的最大值。
推式子：
$$
\begin{aligned}
&\sum\limits_{i = 0}^{n - 1} s_i \times d_i\\
=& s_0 \times d_0 + \sum\limits_{i = 1}^{n - 1} s_i \times (d_0 + \sum\limits_{j = 0}^{i - 1} w_j)\\
=& d_0 \times \sum\limits_{i = 0}^{n - 1} s_i + \sum\limits_{i = 1}^{n - 1} s_i \times \sum\limits_{j = 0}^{i - 1} w_j\\
=& \sum\limits_{j = 0}^{n - 1} w_j \times \sum\limits_{i = j + 1}^{n - 1} s_i
\end{aligned}
$$
设 $a_j = \sum\limits_{i = j + 1}^{n - 1} s_i$，$a_i$ 是不变的。则答案为 $\sum\limits_{i = 0}^{n - 1} w_i \times a_i$。
因此，问题转化为：求满足 $-l_i \le w_i \le l_i$ 且 $\sum\limits_{i = 0}^{n - 1} w_i = 0$ 的 $w_i$ 方案中，$\sum\limits_{i = 0}^{n - 1} w_i \times a_i$ 的最大值。
先抛开 $\sum\limits_{i = 0}^{n - 1} w_i = 0$ 的限制。由于 $a_i$ 有正有负，肯定是贪心地令 $a_i < 0$ 的 $w_i = -l_i，a_i \ge 0$ 的 $w_i = l_i$，设该答案为 $A$。
然后考虑这个限制。设 $neg$ 表示 $a_i < 0$ 的 $-w_i$ 之和，$pos$ 表示 $a_i \ge 0$ 的 $w_i$ 之和。
若 $a_i < 0$ 的 $w_i$ 加一，会使答案减少 $-a_i$，该 $w_i$ 可以从 $-l_i$ 加到 $l_i$，最多加 $2 \times l_i$ 次。
若 $a_i \ge 0$ 的 $w_i$ 减一，会使答案减少 $a_i$，该 $w_i$ 可以从 $l_i$ 减到 $-l_i$，最多减 $2 \times l_i$ 次。
如果 $neg > pos$，希望选择一些 $a_i < 0$ 的 $w_i$ 增加一些值，增加的总次数为 $k = neg - pos$。
等价于有 $2 \times l_i$ 个 $-a_i(a_i < 0)$，前 $k$ 小的数之和为 $B$，则答案为 $A - B$。
如果 $neg \le pos$，希望选择一些 $a_i \ge 0$ 的 $w_i$ 减少一些值，减少的总次数为 $k = pos - neg$。
等价于有 $2 \times l_i$ 个 $a_i(a_i \ge 0)$，前 $k$ 小的数之和为 $B$，则答案为 $A - B$。
开权值线段树，以 $a_i$ 为下标（或者 $-a_i$）。线段树上二分求前 $k$ 小之和即可。注意 $0 \le a_i \le m$，线段树开到 $m$ 不是 $n$。
```cpp
const int N = 200005;
int n, m, q;
int l[N], s[N], a[N];
struct segment_tree{
int sum[N << 2], cnt[N << 2];
#define ls x << 1
#define rs x << 1 | 1
void add(int x, int l, int r, int t, int c, int val){
if(l == r){
sum[x] += c * val;
cnt[x] += c;
return ;
}
int mid = (l + r) >> 1;
if(t <= mid) add(ls, l, mid, t, c, val);
else add(rs, mid + 1, r, t, c, val);
sum[x] = sum[ls] + sum[rs];
cnt[x] = cnt[ls] + cnt[rs];
}
int ask(int x, int l, int r, int k){
if(l == r) return min(cnt[x], k) * l;
int mid = (l + r) >> 1;
if(k <= cnt[ls]) return ask(ls, l, mid, k);
else return sum[ls] + ask(rs, mid + 1, r, k - cnt[ls]);
}
}NEG, POS;
int A, B;
int neg, pos;
inline void update(int i, int k){
if(a[i] < 0){
NEG.add(1, 0, m, -a[i], k * 2 * l[i], -a[i]);
A += k * a[i] * (-l[i]);
neg += k * l[i];
}
else{
POS.add(1, 0, m, a[i], k * 2 * l[i], a[i]);
A += k * a[i] * l[i];
pos += k * l[i];
}
}
signed main(){
n = read(), m = read(), q = read();
for(int i = 0; i < n; i++) l[i] = read();
for(int i = 0; i < m; i++){
int x = read(), y = read();
++s[x], --s[y];
}
for(int i = n - 2; i >= 0; i--) a[i] = a[i + 1] + s[i + 1];
for(int i = 0; i < n; i++) update(i, 1);
for(; q; q--){
int i = read();
update(i, -1);
l[i] = read();
update(i, 1);
if(neg > pos) B = NEG.ask(1, 0, m, neg - pos);
else B = POS.ask(1, 0, m, pos - neg);
print(A - B), putchar('\n');
}
return 0;
}
```