杂题选讲

DerRichter · 2026-08-11 12:44:34 · 算法·理论

update 2026.8.19：为了平衡篇幅，把部分文章移至第二篇。

声明 & 前言

本文基本纯手打，GenAI 贡献不超过 10%。

正如标题所言，这篇文章挑选一些杂题讲解。这些题没有统一的分类，也没有固定的算法模板（除了那几道根号分治），但特征是都有一些思维难度，或是证明复杂度较难（根号分治），也就是思维题选讲了，如某个题遇到了你不会的算法或数据结构，直接跳过即可。

这篇文章也是我个人的习题总结。写这篇文章的原因，是发现以前做过的很多难题/思维题不记得做法了，问了同学，或者看代码回忆起来了，就都写在这里了，以免忘记。

这篇文章应该会动态更新，不然后面做的题又得忘了。

题目基本按照难度递增排列。

正文

[ABC342G] Retroactive Range Chmax

题意

给定序列 A，Q 次操作：

• 1 l r x 修改：a_i \leftarrow \max (a_i, x), \ l \le i \le r；
• 2 i 撤销：撤销第 i 次操作；
• 3 i 查询 A_i。

思路

线段树。如果直接做的话，会发现撤销操作极难实现，且区间取 \max 也难以把 tag 应用。

那就不要应用 tag 了。我们可以用一个 set 把所有 tag 存下来，撤销时只需按照修改的方式，递归到节点，直接删除 tag 即可。因为我们需要删除 tag，所以这里的标记不能下传，即所谓的标记永久化技巧。

P6374 「StOI-1」 树上询问

题意

给定 n 个点的树，q 次查询，每次查询一个三元组 (a, b, c)，问有多少个点满足，在以这个点为根时，c 是 a, b 的 LCA。

思路

做法很多，这里讲解重剖做法。

分别找到 a, b 方向上离 c 最近的点 A, B，减去其子树大小即可。父亲子树大小为 n - sz_c。

树剖 LCA 写法可以使用如下代码寻找 A, B：

int get(int u, int v) {
  if (lca(u, v) != u) return f[u];
  else {
    if (lca(v, son[u]) == son[u]) return son[u];
    else {
      for (; f[top[v]] != u; v = f[top[v]]);
      return top[v];
    }
  }
}

这是我做题的时候在讨论区看到的，忘了是哪一位大佬了。

P8366 [LNOI2022] 题

题意

给定长度为 3 n、值域为 [0, 3] 的整数序列 S = s_1 s_2 \cdots s_{3 n}。你需要首先将 S 中的每个 0 替换为 [1, 3] 中的任意一个整数，得到序列 T = t_1 t_2 \cdots t_{3 n}，然后给出 n 个长度为 3 的整数序列 {\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}，使得

思路

动态规划。

显然只有排列 213, 132, 321 满足条件。我们将状态设为 dp_{i, a, b, c, d, e, f}，六个字母分别表示当前有多少个已匹配的 1, 2, 3, 21, 13, 32，dp 值就表示方案数了。

当 s_i = 0/1 时，转移如下：

当 s_i = 0/2 时，转移如下：

当 s_i = 0/3 时，转移如下：

答案即为 dp_{n, 0, 0, 0, 0, 0, 0} \times n!，乘上 n! 是因为之前忽略了顺序导致的新方案。

CF2126G2 Big Wins! (hard version)

题意

给定长为 N 的序列 a，且 a_i \le n，求 \text {med} - \min 最大的子段，即中位数减去最小值最大。这里，中位数指的是排序后的第 \lceil \frac {k + 1} 2 \rceil 个数，其中 k 为数组长度。

思路

中位数很麻烦，但是 \min 却是很简单。可以用单调栈处理出当前数可以作为最小值的最大区间，设其端点为 L_i, R_i。

现在来考虑中位数。一个经典 trick 是，把 \lt \text {x} 的数看作 -1，\ge \text {x} 的数看作 1，那么中位数就是满足和 \ge 0 的最小 x。这个是容易证明的。

于是我们可以考虑二分中位数。这里可以使用主席树维护。因为 a_i \le n，所以不用离散化，可以直接对 1 \sim n 的每个整数开一个版本。但这里，我们要得到最大中位数，所以我们应该判断，是否能够构造出一个 [L_i, R_i] 的子区间 [l_i, r_i]，使得按照上面的方式建主席树后，[l_i, r_i] 的区间和 \ge 0。这个和可以拆解为 [L_i, i - 1] 的最大后缀和加上 [i + 1, R_i] 的最大前缀和再加上 a_i 按照上面的方式变为的 -1/1。如果这个和 \ge 0，那么说明当前二分到的这个值是成立的，否则不成立。

时间复杂度 O(n \log ^ 2n)，本题不卡常，大常数选手稍微注意细节也可通过。

HDU6701 Make Rounddog Happy

题意

给定数列 a_1,a_2,\dots,a_n，满足 1 \le a_i \le n。

定义一个好子数组需要满足：该子段 a_l,a_{l+1},\dots,a_r 内所有元素互不相同且 \max(a_l,a_{l+1},\dots,a_r) − (r−l+1)\le k 。

请计算 a 中好子数组的总数量。

思路

如果我们直接枚举左端点，再计算右端点数量的话，会发现无法计算。但是我们稍稍移个项：

就会发现，当最大值确定的时候，可以直接统计合法长度的数量，或者说，长度确定的时候，可以直接统计合法的最大值数量。

但是，还有另一个条件：所有元素互不相同。这个条件就可以 ban 掉大部分你在看到上面这句话之后产生的想法。比如单调栈维护左右端点，都无法解决元素不重复这个问题。

好在天无绝人之路，我们发现，把最大值单拎出来，左右两个区间是两个互不相干的子问题。所以考虑启发式分治。

我们每次找到最大值位置，计算短区间对长区间的贡献。容易知道这样是 O(n \log n) 的，具体证明就不写了。

如何计算贡献？枚举左/右端点（左还是右分类讨论，短区间在左就是左端点，反之同理），那么另一个端点只要满足长度限制就好了。如何解决重复元素问题？我们提前预处理出，对于每个元素，其合法的左/右端点最远能到哪里。具体地，记录每个元素最后出现的位置，枚举到 i 的时候，当前左/右端点就是上一个或者 a_i 的上一次出现位置，哪个更近取哪个。

P2617 Dynamic Rankings

题意

给定长度为 n 的数列 \{ a_n \}，m 次操作，每次操作如下：

• Q l r k 查询：查询区间 [l, r] 内的第 k 小；

• C x y 修改：a_x \leftarrow y。

思路

主席树本质是 n 个前缀和，而要修改的话，就得要修改后缀。那什么数据结构能够维护前/后缀修改单点查询呢？树状数组。

树状数组的原理是 c_x 表示 [x - \text{lowbit} (x) + 1, x] 的和，而类似的，我们可以让这里的树状数组换一个意思，让 c_x 为区间 [x - \text{lowbit}(x) + 1, x] 的权值线段树。这就是树套树的一种：树状数组套主席树。

修改时，相当于是在 \log n 棵主席树上修改，查询时，相当于 \log n 棵主席树作差。具体地，修改时，直接按照树状数组修改的方式，在主席树上操作；查询时，传两个 vector 进函数，一个是左端点的前缀的所有 root，另一个是右端点的，递归时每次往后移动一位即可。

CF1009F Dominant Indices

题意

给定一棵树，定义数组 \{ d_{u, i} \} 为 u 的子树中，离 u 的距离为 i 的点个数，对于每个 u，求 \{ d_{u, i} \} 最大值的下标，若有多个，取最小的。

思路

长链剖分优化 dp。

可以先设 dp_{u, i} 表示 u 子树下离 u 距离为 i 的结点数量，转移如下：

但是这样显然是 O(n ^ 2) 的，于是考虑优化。我们可以对每一个结点开一个 vector，这样更新的时候就相当于是 v 的 vector 向后移一位，这样虽然看起来对优化没有什么帮助，但是我们可以每次传一个指针，每次继承重儿子的答案，再合并其他轻儿子。

因为这样做每条长链都恰好被合并了一次，所以是 O(n) 的。

void dfs2(int u, vector<int>::iterator dp) {
  dp[0]++;
  if (son[u]) {
    dfs2(son[u], dp + 1);
    ans[u] = ans[son[u]] + 1;
  }
  for (int v : g[u]) {
    if (v == f[u] || v == son[u]) continue;
    vector<int> ndp(high[v], 0);
    dfs2(v, ndp.begin());
    for (int j = 0; j < high[v]; j++) {
      dp[j + 1] += ndp[j];
      if (dp[j + 1] > dp[ans[u]]) {
        ans[u] = j + 1;
      } else if (dp[j + 1] == dp[ans[u]]) {
        ans[u] = min(ans[u], j + 1);
      }
    }
  }
  if (dp[0] >= dp[ans[u]]) ans[u] = 0;
}

CF1709E XOR Tree

题意

给定一棵 n 个点的树，每个点有一个点权 a_i，每次操作可以修改任意一个点的点权为任意一个正整数。求要使没有任何一条简单路径上所有点的异或和为 0，最少需要多少次操作。

思路

首先，任意两点间的异或和可以表示成：

其中 u 为 x, y 的 LCA，d_x 表示从根节点到 x 的异或和。

题目要求上面的式子不能等于 0，也即不能存在 d_y，使得 d_y = d_x \oplus a_u 且 x, y 位于 u 的两个不同的儿子的子树内。

假设我们已经找到了一组不满足条件的 (u, x, y)，那么在哪里修改能够使得答案最小？答案是在 u 处。因为题目对于修改后的数字没有要求，所以我们可以改成一个极大的、唯一的数字，这样的数总是存在。为什么这样是最优的呢？因为这样不仅能够解决 (x, y) 的问题，后面 x 的子树内，如果还有不满足条件的路径的话，一样会带上 a_u 这个极大值，也就一定不会再出现非法路径了。

如何快速找到非法路径？我们可以用 set 维护每个点的子树中所有的 d_x。在向父亲合并信息的时候，就用启发式合并，如果存在 d_y = d_x \oplus a_u，可以直接计入答案。合并后，子树的信息可以直接清空。这样整体时间复杂度是 O(n \log ^ 2 n) 的。

P13984 数列分块入门 9

题意

给定长为 n 的数列，n 次询问，每次询问区间众数。

思路

分块。如果直接分块，记录每个块的信息的话，会发现在时空复杂度正确的情况下，无法合并块与块的信息。

我们考虑分开计算，具体地，答案可能为完整块内的数，也可能为不完整块内的数。对于不完整块内的数，可以直接记录出现位置，每次枚举并二分计算出现次数即可。现在问题在于，完整块内的数，该如何计算贡献？

注意到，若一个数在完整块内出现过，在非完整块内也出现过，那么直接把它当作非完整块的数处理即可，因为如果我们只考虑这些数在完整块内的出现次数，那么一定不会比暴力计算的答案更优。所以我们可以以块为单位，维护任意两个块之间的众数。查询时枚举不属于完整块的数，计算出现次数并取 max 即可。

CF848C Goodbye Souvenir

题意

给定一个长度为 n 的序列 a，m 次操作，每次操作形式如下：

• 1 p x 修改：a_p \leftarrow x；
• 2 l r 询问：区间中每个数的最后一次和第一次出现位置的差之和。

思路

CDQ 分治。

设数 x 出现位置为 p_{x, 1}, \dots, p_{x, k}。

则区间 [L, R] 的答案为 p_{x, r} - p_{x, l}，其中 l 满足：不存在 1 \le l' \lt l 使得 p_{x, l'} \ge L，r 满足：不存在 r \lt r' \le k，使得 p_{x, r'} \le R。

而同时，答案又可表示为 \sum \limits_{i = l + 1} ^ r p_{x, i} - p_{x, i - 1}。

修改的时候，实际上就是单点更新。我们可以把所有数的出现位置存下来，每次修改时，只需把这个数 a_p 原本的答案（即 a_p 减前驱/后继减 a_p）都打上 -1 的 flag，修改后再把新的加上即可。

查询时，需要统计所有 pre \ge l 和 now \le r 的答案，不管 flag 是 -1/1。注意不要把查询也算进去了。