## 二小姐的烟花
#贪心 #结论 #排序
首先，如果我们选择了若干个烟花进行燃放，那么按照 $a_i$ 从小到大的顺序燃放一定是最优的。因为 $a_i$ 的和本身确定了，而这种构造方案能够获得最多的顺序对。
所以先对 $a$ 从小到大排个序。现在，我们可以很显然地猜出一个结论：最优的燃放烟花的方式一定是燃放最后的若干个烟花。证明不会证，只能感性理解。
于是我们就从后往前遍历，计算贡献。假如当前的 $a_i$ 出现了 $x$ 次，那么它会增加 $n-i+1-x$ 个逆序对。我们对这个值进行累加，再乘上 $k$，最后加上 $a_i$ 本身的值，就能得到燃放 $i\sim n$ 的烟花能获得的最大值了，最后求最值。
时间复杂度 $\mathcal O(n\log_2 n)$，瓶颈在排序。
```cpp
#include <fstream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
ifstream cin("flandre.in");
ofstream cout("flandre.out");
struct {
LL x, id;
} a[kMaxN];
LL n, k, sum, cnt, eql, p, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (LL i = 1; i <= n; i++) {
cin >> a[i].x;
a[i].id = i;
}
sort(a + 1, a + n + 1, [](auto a, auto b) {
return a.x < b.x;
});
p = n + 1;
for (LL i = n; i >= 1; i--) {
if (i == n || a[i].x != a[i + 1].x) {
eql = 1;
} else {
eql++;
}
sum += a[i].x;
cnt += n - i + 1 - eql;
LL val = sum + k * cnt;
if (val > ans) {
ans = val;
p = i;
}
}
cout << ans << ' ' << n - p + 1 << '\n';
for (LL i = p; i <= n; i++) {
cout << a[i].id << ' ';
}
return 0;
}
```
## 红美铃摸鱼
#数学 #前缀和
看到
$
\sum\limits_{l=1}^n\sum\limits_{r=l}^n\left[\left(\sum_{i=l}^r a_i\right)\times\left(\sum_{i=l}^r b_i\right) \right]
$
这个一大坨式子，我们就可以考虑拆贡献。对于 $a_i$ 和 $b_j$，如果它俩相乘的话，那么有 $l\in [1,\min(i,j)]$ 和 $r\in [\max(i,j),n]$。显然我们不能枚举 $i$ 和 $j$ 进行计算，而 $q$ 次操作每次都是对 $b$ 进行区间相加。于是我们可以想到
- [I] 预处理每个 $b_i$ 所乘上的系数，即 $\sum\limits_{j=1}^n\left(\min(i,j)\times (n-\max(i,j)+1)\times a_j\right)$。
这个式子有 $\min$ 和 $\max$，不好搞，所以我们把 $j$ 分成 $[1,i]$ 和 $[i,n]$ 的分别进行处理。
对于 $j\in [1,i]$，式子变成 $\sum\limits_{j=1}^i j\times(n-i+1)\times a_j$。我们从左往右枚举 $i$，每次添加 $j=i$ 的一个新元素。不难发现 $n-i+1$ 随着 $i$ 变大而变小，具体是每次 $i\gets i+1$ 时原来所有的 $j$ 的贡献都会减掉 $j\times a_j$。
所以我们在增加 $j=i$ 的贡献时，同时维护 $\sum\limits_{j=1}^{i-1}j\times a_j$，每次累加这个值，从总贡献当中减去。因此，我们就成功完成了 $j\in [1,i]$ 的这一部分。
对于 $j\in [i,n]$ 同理，从后往前遍历，注意 $\max$ 和 $\min$ 互换了。这些预处理都是 $\mathcal O(n)$ 的。
最后每个 $j=i$ 多累加了一次，从贡献中删去 $i(n-i+1)a_i$ 即可。这下我们就可以轻松地得出初始答案，每次查询对 $[l,r]$ 的 $b$ 值加上 $k$ 也就相当于再答案上累加了 $[l,r]$ 的系数之和乘上 $k$。这个可以通过前缀和实现
时间复杂度 $\mathcal O(n+q)$，要注意常数。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 5e5 + 5, kMod = 1e9 + 7;
ifstream cin("meirin.in");
ofstream cout("meirin.out");
LL a[kMaxN], b[kMaxN], base[kMaxN], n, q, sum, sub, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
sum = ((sum + (n - i + 1) * i % kMod * a[i] % kMod - sub) % kMod + kMod) % kMod;
base[i] = (base[i] + sum + kMod) % kMod;
sub = (sub + i * a[i] % kMod + kMod) % kMod;
}
for (LL i = 1; i <= n; i++) {
cin >> b[i];
}
sum = sub = 0;
for (LL i = n; i >= 1; i--) {
sum = ((sum + i * (n - i + 1) % kMod * a[i] % kMod - sub) % kMod + kMod) % kMod;
base[i] = (base[i] + sum + kMod) % kMod;
sub = (sub + (n - i + 1) * a[i] % kMod + kMod) % kMod;
}
for (LL i = 1; i <= n; i++) {
base[i] = (base[i] - i * (n - i + 1) % kMod * a[i] % kMod + kMod) % kMod;
ans = (ans + base[i] * b[i] % kMod + kMod) % kMod;
base[i] = (base[i - 1] + base[i] + kMod) % kMod;
}
for (LL l, r, k; q; q--) {
cin >> l >> r >> k;
ans = (ans + (base[r] - base[l - 1] + kMod) % kMod * k % kMod + kMod) % kMod;
cout << ans << '\n';
}
return 0;
}
```
## 红魔馆
#概率与期望 #树形dp #组合数学
- [!] 以下规定 $m$ 个关键点的行走方式为路线，任意两点间的为路径。
首先我们需要先求出初始答案。按照每一条遍历方式求总和肯定是不可取的，于是仍然考虑拆贡献。本题没有对走的路线进行任何规定，所以任何两个属于 $m$ 个关键点的点都可以连起来，作为路线的一部分。
对于任意一条两个关键点连起来的路径，它会在 $\sum\limits_{i=0}^m A_{m-2}^i\times(m-2-i)!$ 条路线当中出现过。即枚举路径前有 $i$ 个关键点经过，则有 $A_{m-2}^i$ 种排列方式，剩下 $(m-2-i)$ 个点放在后面随便排。
- [I] 事实上这个数等于 $(m-1)!$，但是我赛时没管这么多，写的暴力求和。
现在我们考虑如何计算任意两个关键点之间的距离之和。考虑树形 dp，设 $dp_i$ 表示以 $i$ 为起点，到 $i$ 子树中所有关键点所需要的距离之和。若 $p_i$ 为 $i$ 子树中的关键点之和，那么有
$
dp_i=\sum_{j\in\operatorname{son}(i)}(dp_j+w(i,j)\times p_j)
$
其实就是将 $j$ 到 $j$ 子树内的关键点的距离拼上 $w(i,j)$。不过我们求的不是 $i$ 到 $i$ 子树内，而是 $i$ 到任意关键点（除 $i$ 本身）的距离和。
考虑换根，把每个 $i$ 看作根，计算 $i$ 到树内任意关键点的距离和。设其为 $res_i$。如果要将根从 $i$ 转移到 $j$ 的话，$j$ 子树内的所有关键点到根的距离就会减去 $w(i,j)$，其余的所有关键点到根的距离就会加上 $w(i,j)$，所以有
$
res_j=res_i-p_j\times w(i,j)+(m-p_i)\times w(i,j)~(j\in\operatorname{son}(i))
$
此时我们就通过 $\mathcal O(n)$ 计算出了每个点到任意关键点之间的距离之和，那么把所有关键点的这个值累加起来即可得到路径距离总和。乘上之前的系数 $\sum\limits_{i=0}^m A_{m-2}^i\times(m-2-i)!$ 或 $(m-1)!$ 即可得到任意的路线距离总和的总和，除以总路线数量 $m!$ 即可得到初始答案。
现在考虑修改。如果我们修改一个点 $x$ 邻边边权增加 $k$，而它的邻边被任意两个关键点之间的路径经过的次数为 $a_x$，那么答案会加上 $a_x\times k$（还要乘上系数和 $m!$）。
如何求 $a_x$ 呢？如果 $x$ 是关键点，那么它会被经过 $2(m-1)$ 次（$x$ 到其它关键点和其它关键点到 $x$）。其次是作为路径上的点，那么可以遍历 $x$ 的所有邻点 $i$，获取以 $x$ 根 $i$ 子树内关键点的数量（仅当 $i=\operatorname{fa}(x)$ 时有区别，其余都是 $p_i$），然后对于任意两个不同 $i$ 的数量相乘再乘 $2$（不是一正一反，而是经过了 $x$ 的两条邻边）。当然肯定不能枚举，具体操作是求和后平方，再减去每个项的平方。
现在我们就成功写出这道题了。时间复杂度 $\mathcal O(n+q)$，也是需要注意常数的一道题。
```cpp
#include <fstream>
#include <forward_list>
#include <utility>
using namespace std;
using LL = long long;
const LL kMaxN = 5e5 + 5, kMod = 998244353;
ifstream cin("sakuya.in");
ofstream cout("sakuya.out");
LL dp[kMaxN], res[kMaxN], ptr[kMaxN], mrk[kMaxN], fac[kMaxN], inv[kMaxN], a[kMaxN], fa[kMaxN], n, m, q, ans;
forward_list<pair<LL, LL>> e[kMaxN];
void dfs1(LL x, LL f) {
ptr[x] = mrk[x];
fa[x] = f;
for (const auto &i : e[x]) {
if (i.first == f) {
continue;
}
dfs1(i.first, x);
ptr[x] += ptr[i.first];
dp[x] = (dp[x] + dp[i.first] + ptr[i.first] * i.second % kMod) % kMod;
}
}
void dfs2(LL x, LL f) {
for (const auto &i : e[x]) {
if (i.first == f) {
continue;
}
res[i.first] = res[x] - (ptr[i.first] * i.second) + (m - ptr[i.first]) * i.second;
res[i.first] = (res[i.first] % kMod + kMod) % kMod;
dfs2(i.first, x);
}
}
LL pow(LL a, LL b) {
LL res = 1;
for (; b; b /= 2) {
b % 2 && (res = res * a % kMod);
a = a * a % kMod;
}
return res;
}
LL A(LL n, LL m) {
if (m > n) {
return 0;
}
return fac[n] * inv[n - m] % kMod;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_front(v, w);
e[v].emplace_front(u, w);
}
fac[0] = inv[0] = 1;
for (LL i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % kMod;
}
inv[n] = pow(fac[n], kMod - 2);
for (LL i = n - 1; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % kMod;
}
for (LL i = 1, x; i <= m; i++) {
cin >> x;
mrk[x]++;
}
dfs1(1, 0);
res[1] = dp[1];
dfs2(1, 0);
for (LL i = 1; i <= n; i++) {
ans = (ans + mrk[i] * res[i] % kMod) % kMod;
}
LL base = 0;
for (LL i = 0; i <= m - 2; i++) {
base = (base + A(m - 2, i) * fac[m - 2 - i] % kMod) % kMod;
}
for (LL i = 1; i <= n; i++) {
mrk[i] && (a[i] = 2 * mrk[i] % kMod * (m - 1) % kMod);
LL sum = 0, sub = 0;
for (const auto &j : e[i]) {
if (j.first == fa[i]) {
LL x = m - ptr[i];
sum = (sum + x) % kMod;
sub = (sub + x * x % kMod) % kMod;
} else {
LL x = ptr[j.first];
sum = (sum + x) % kMod;
sub = (sub + x * x % kMod) % kMod;
}
}
sum = (sum * sum % kMod - sub + kMod) % kMod;
a[i] = (a[i] + 2 * sum % kMod) % kMod;
}
cin >> q;
for (LL x, k; q; q--) {
cin >> x >> k;
ans = (ans + a[x] * k % kMod) % kMod;
cout << ans * base % kMod * inv[m] % kMod << '\n';
}
return 0;
}
```
## 红楼
#分治 #分块 #差分
我在考场上想出了根号分治，但是没有优化掉 $\log$。
首先题目中的修改操作可以视作以 $x$ 为一个周期，每个周期前 $y+1$ 个数加上 $k$。
- 对于 $x>\sqrt{n}$，我暴力枚举每一个周期，用线段树做区间加法。修改时间复杂度 $\mathcal O(\sqrt n\log_2 n)$，查询 $\mathcal O(\log_2 n)$。
- 对于 $x\le \sqrt{n}$，我对于每个 $x\le \sqrt n$ 都会开一颗 $\sqrt n$ 大小的线段树（维护和还有下标乘平方的和），然后对于 $x$ 线段树的前 $\min(x,y+1)$ 个数加上 $x$。查询时枚举每一个 $x$，然后先把整块的给加上，最后剩的一些对于所有 $y\ge res$ 的系数都会被限制在 $y$。修改时间复杂度 $\mathcal O(\log_2\sqrt n)$，查询时间复杂度 $\mathcal O(\sqrt{n}\log_2 \sqrt{n})$。
不难发现复杂度瓶颈在于第一种操作的修改。我们需要 $\mathcal O(1)$ 对一个区间进行加法（这样单词修改就变成了 $\sqrt n$），而查询时间复杂度可以变成 $\mathcal O(\sqrt n)$。
这是一个相当复杂的分块，需要使用复杂的差分+前缀和技巧实现。不详细说了。
对于第二种操作，修改时间复杂度太优了查询复杂度太劣，所以不开 $\mathcal O(\sqrt n)$ 的线段树了，直接 $\mathcal O(\sqrt n)$ 暴力修改前缀和数组，这样单块内查询就能做到 $\mathcal O(1)$。总时间复杂度就可以达到 $\mathcal O(m\sqrt n)$。