声明 & 前言

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

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

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

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

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

正文

[ABC342G] Retroactive Range Chmax

题意

给定序列，次操作：

1 l r x 修改：；
2 i 撤销：撤销第次操作；
3 i 查询。

思路

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

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

P6374 「StOI-1」树上询问

题意

给定个点的树，次查询，每次查询一个三元组，问有多少个点满足，在以这个点为根时，是的 LCA。

思路

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

分别找到方向上离最近的点，减去其子树大小即可。父亲子树大小为。

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

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] 题

题意

给定长度为、值域为的整数序列。你需要首先将中的每个替换为中的任意一个整数，得到序列，然后给出个长度为的整数序列，使得

，；
，；
，是的一个排列且逆序对数为奇数。

思路

动态规划。

显然只有排列满足条件。我们将状态设为，六个字母分别表示当前有多少个已匹配的，值就表示方案数了。

当时，转移如下：

答案即为，乘上是因为之前忽略了顺序导致的新方案。

CF2126G2 Big Wins! (hard version)

题意

给定长为的序列，且，求最大的子段，即中位数减去最小值最大。这里，中位数指的是排序后的第个数，其中为数组长度。

思路

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

现在来考虑中位数。一个经典 trick 是，把的数看作，的数看作，那么中位数就是满足和的最小。这个是容易证明的。

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

时间复杂度，本题不卡常，大常数选手稍微注意细节也可通过。

HDU6701 Make Rounddog Happy

题意

给定数列，满足。

定义一个好子数组需要满足：该子段内所有元素互不相同且
。

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

思路

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

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

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

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

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

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

P2617 Dynamic Rankings

题意

给定长度为的数列，次操作，每次操作如下：

Q l r k 查询：查询区间内的第小；
C x y 修改：。

思路

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

树状数组的原理是表示的和，而类似的，我们可以让这里的树状数组换一个意思，让为区间的权值线段树。这就是树套树的一种：树状数组套主席树。

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

CF1009F Dominant Indices

题意

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

思路

长链剖分优化 dp。

可以先设表示子树下离距离为的结点数量，转移如下：

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

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

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

题意

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

思路

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

其中为的 LCA，表示从根节点到的异或和。

题目要求上面的式子不能等于，也即不能存在，使得且位于的两个不同的儿子的子树内。

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

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

P13984 数列分块入门 9

题意

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

思路

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

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

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

CF848C Goodbye Souvenir

题意

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

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

思路

CDQ 分治。

设数出现位置为。

则区间的答案为，其中满足：不存在使得，满足：不存在，使得。

而同时，答案又可表示为。

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

查询时，需要统计所有和的答案，不管 flag 是。注意不要把查询也算进去了。

P8078 [WC2022] 秃子酋长

题意

给定一个排列，每次查询：把区间排序后，相邻两个数在原序列内位置差之和。

思路

回滚莫队。

你会发现这题线段树比较难实现，区间合并很难，但是又考虑到这题时限较宽（5s），可以过做法，所以考虑莫队。

若我们考虑普通莫队，可以对每个数存它的的出现位置，再开一个链表维护所有位置的有序列表，每次扩展区间的时候，就可以在链表中找到当前数的前驱后继，贡献容易算出。这样是的。稍微算一算，炸了。

但是我们注意到，因为我们对每个数分别存了出现位置，所以，在不考虑 set 的情况下，我们的删除操作可以做到。于是可以想到只删除不增加的回滚莫队，时间复杂度。

本题卡常。

[ABC405G] Range Shuffle Query

题意

给定长为的序列，次询问，每次询问，表示子段中，去掉的元素后，将剩下的子段中的元素重排，能够得到的不同序列数量。

思路

首先，答案可以表示为

于是，问题转化为求区间内小于等于给定值的出现个数。

但是，如果直接莫队+树状数组动态维护的话，时间复杂度是的，炸了。于是我们需要换一种思路。

注意到，时间复杂度的瓶颈在于，每次扩展/收缩区间都需要的时间，而总共有次端点移动。但是查询总共只有次，所以我们可以换一种修改很快，查询可以稍慢一点的数据结构。

能够想到值域分块。修改时只需修改当前点和块内的总和/积，查询时枚举完整块的和/积再并上非完整块部分的即可。

此时，我们修改的时间复杂度来到了，而查询是，但总时间复杂度降了下来，，这也是一种平衡吧。

[ABC259Ex] Yet Another Path Counting

题意

给定的矩阵，求：满足起点和终点的数相等的不同的路径数量。

思路

显然，对于任意两个点，我们可以地求出答案：。若点集大小为，则这个做法是的。

我们还有一个做法：确定一个起点，然后 dp。

但是，如果我们直接枚举颜色，对所有的颜色都用同一种方法暴力求的话，是的，TLE。

考虑根号分治。对于点集大小的颜色，易知其最多有个，用第一种求法，时间复杂度。

对于点集大小的颜色，这时候显然就不能直接做了，此时的 dp 更优。下面证明这部分的时间复杂度。

设点集大小大于的颜色共有种，则所有满足条件的点集大小之和，又总共只有个点，所以，结合上面两式，得，则这部分的时间复杂度为。

综上，总时间复杂度为，由均值不等式知，，在时等号成立。证毕。

所以，将作为阈值，根号分治即可。

P1989 【模板】无向图三元环计数

题意

给定一张有个点条边的无向图，求其三元环个数。

思路

先说结论。我们可以按照如下方式给这张图定向：

对于一条边，

若，则定方向为；
若，则方向为编号小的结点到编号大的结点。

下面给出证明。

我们先证引理：在定向后的有向无环图中，任意节点的出度。证明如下：

假设节点的出度为，即。

根据定向规则，对于的任意出边邻居，必有。

因为节点有个相邻节点，所以对于这个出邻居，它们的无向图度数满足：

显然原无向图中所有节点的度数之和为。考虑到节点及其个出邻居，这个节点的度数和不能超过全图总度数：

即：

因此，任意节点的出度满足。

根据引理，在定向后的图上，我们可以枚举点，直接标记的邻域，然后枚举出点，再枚举的出点，若在的邻域内，则算入答案。

杂题选讲