2025.10.10 模拟赛

二小姐的烟花

贪心 结论 排序

首先，如果我们选择了若干个烟花进行燃放，那么按照 $a_i$ 从小到大的顺序燃放一定是最优的。因为 $a_i$ 的和本身确定了，而这种构造方案能够获得最多的顺序对。

所以先对 $a$ 从小到大排个序。现在，我们可以很显然地猜出一个结论：最优的燃放烟花的方式一定是燃放最后的若干个烟花。证明不会证，只能感性理解。

于是我们就从后往前遍历，计算贡献。假如当前的 $a_i$ 出现了 $x$ 次，那么它会增加 $n-i+1-x$ 个逆序对。我们对这个值进行累加，再乘上 $k$，最后加上 $a_i$ 本身的值，就能得到燃放 $i\sim n$ 的烟花能获得的最大值了，最后求最值。

时间复杂度 $\mathcal{O}(n{\log }_{2}n)$，瓶颈在排序。

#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 _{l=1}^n\sum _{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 _{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 _{j=1}^{i}j\times (n-i+1)\times a_j$。我们从左往右枚举 $i$，每次添加 $j=i$ 的一个新元素。不难发现 $n-i+1$ 随着 $i$ 变大而变小，具体是每次 $i\leftarrow i+1$ 时原来所有的 $j$ 的贡献都会减掉 $j\times a_j$。

所以我们在增加 $j=i$ 的贡献时，同时维护 $\sum _{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)$，要注意常数。

#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 _{i=0}^m{A}_{m-2}^i\times (m-2-i)!$ 条路线当中出现过。即枚举路径前有 $i$ 个关键点经过，则有 $A_{m-2}^i$ 种排列方式，剩下 $(m-2-i)$ 个点放在后面随便排。

• [I] 事实上这个数等于 $(m-1)!$，但是我赛时没管这么多，写的暴力求和。

现在我们考虑如何计算任意两个关键点之间的距离之和。考虑树形 dp，设 $d{p}_i$ 表示以 $i$ 为起点，到 $i$ 子树中所有关键点所需要的距离之和。若 $p_i$ 为 $i$ 子树中的关键点之和，那么有

$$d{p}_i=\sum _{j\in \mathrm{son}(i)}(d{p}_j+w(i,j)\times p_j)$$

其实就是将 $j$ 到 $j$ 子树内的关键点的距离拼上 $w(i,j)$。不过我们求的不是 $i$ 到 $i$ 子树内，而是 $i$ 到任意关键点（除 $i$ 本身）的距离和。

考虑换根，把每个 $i$ 看作根，计算 $i$ 到树内任意关键点的距离和。设其为 $re{s}_i$。如果要将根从 $i$ 转移到 $j$ 的话，$j$ 子树内的所有关键点到根的距离就会减去 $w(i,j)$，其余的所有关键点到根的距离就会加上 $w(i,j)$，所以有

$$re{s}_j=re{s}_i-p_j\times w(i,j)+(m-p_i)\times w(i,j)(j\in \mathrm{son}(i))$$

此时我们就通过 $\mathcal{O}(n)$ 计算出了每个点到任意关键点之间的距离之和，那么把所有关键点的这个值累加起来即可得到路径距离总和。乘上之前的系数 $\sum _{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=\mathrm{fa}(x)$ 时有区别，其余都是 $p_i$），然后对于任意两个不同 $i$ 的数量相乘再乘 $2$（不是一正一反，而是经过了 $x$ 的两条邻边）。当然肯定不能枚举，具体操作是求和后平方，再减去每个项的平方。

现在我们就成功写出这道题了。时间复杂度 $\mathcal{O}(n+q)$，也是需要注意常数的一道题。

#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})$。