给定一个字符串集合 $S$，若由 $S$ 中 $k$ 个可相同的字符串拼接而成的字符串 $s$ 恰有 $k$ 个循环移位能由若干 $S$ 中的字符串拼成，则称其为好的。一个集合 $S$ 为好的，当且仅当所有能由 $S$ 中若干可相同的字符串拼接而成的字符串都是好的。给定字符串序列求有多少区间中的字符串集合是好的。

如果一个集合是好的，显然一个集合的所有子集都是好的，所以序列中的任意两个极长区间一定互不包含，可以双指针转化成做 $O(n)$ 次检查某个字符串集合 $S$ 是否是好的（注意这里需要去重）。

我们将“若干字符串拼接后得到两个互为循环移位的字符串 $s_1,s_2$”这个过程用一个图来表示：对集合 $S$ 中的每个字符串的每个非空后缀 $t$ 建两个状态分别表示 $s_1=s_2t$，和 $s_2=s_1t$；建空状态表示 $s_1=s_2$。

对字符串做 z-algorithm，可以 $O((\sum_{x\in S}|x|)^2)$ 地连边。途中有环则说明改集合不合法。

更进一步地，如果某个表示 $s_1=s_2t$ 的状态 $t$ 能够到达表示 $s_2=s_1t$ 的状态，根据对称性，它一定能到达它自己。所以对称的两个状态要么在同一个强连通分量里，要么互不能到达。据此我们可以给每个非空后缀只建一个点。

下文用一个二进制数中为 $1$ 的位来表示一个数。

维护集合 $S$，每次插入一个数后查询集合中两个元素 $x\slash y$ 的最大值。$\slash$ 表示集合差。

我们考虑在每次加入 $x$ 后考虑这个集合的答案是否被 $x\slash y$ 或 $y\slash x$ 更新，其中 $y$ 是集合中原有的数。

对从大到小每一位依此贪心，于是问题就变成了，加入数并动态维护 $S$ 中是否存在 $x$ 的子集和超集。

朴素的暴力是加入一个数，遍历其所有子集和超集分别标记。不过注意到，如果 $S$ 中存在 $x$ 的子集，那么对于 $x$ 的所有超集 $y$，$S$ 中均存在 $y$ 的子集。

所以如果 $S$ 中已经存在 $x$ 的超集则返回，否则对 $x$ 分别去掉每一位后的集合递归地标记。子集同理。这样做的总时间复杂度为 $O(n\log n)$。

给定两个大小相等的集合 $A,B$，求满足 $f(i)\not=i$ 的双射 $f$ 的数量。

若 $A=B$ 则为错排问题，所以我们考虑类似地通过递推解决这个问题。

令 $S=A\cap B$，设 $f(n,m)$ 为 $|S|=n,|A|=|B|=n+m$ 时这样的双射 $f$ 的数量。

显然 $f(0,m)=m!$。$n>0$ 时我们令 $t=\inf S$，对所有 $f$ 按照 $f(t)$ 进行分类讨论：

• 若 $f(t)\in S$ 且 $f(t)=f^{-1}(t)$，显然有这种情况下所有合法 $f$ 到 $A,B$ 均去掉 $t,f(t)$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n-1)f(n-2,m)$
• 否则，通过令 $f^{-1}(t)$ 映射到 $f(t)$，可以得到所有合法 $f$ 到 $A,B$ 均去掉 $t$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n+m)f(n-1,m)$。

由此可以得到递推式 $f(n,m)=(n-1)f(n-2,m)+(n+m)f(n-1,m)$。可见合法的状态只有 $O(n)$ 种。

求若干个首项为 $0$ 公差为 $1$ 的等差数列总和为 $s$ 的情况下长度之和最少为多少。

注意到和不超过 $s$ 的这样的等差数列只有 $\sqrt s$ 种，暴力 DP 即可。

网格图有一个优美的性质，它的最小割的大小等于较短边的长度，不超过 $\sqrt S$，其中 $S$ 为网格图面积。

所以网格图上的最短路可以分治地做，网格上一块矩形区域，在较长边中点处切开。此时两个点间的最短路分为，只经过其中一部分的和跨过切面的。只经过其中一部分的，分治处理；跨过切面的，我们以切面上每个点为源，在整个区域内求最短路。对于一块面积为 $S$ 的矩形区域，所需时间为

$$\displaylines{T(S)=2T\left(\frac S2\right)+\sqrt S\cdot S\log S }$$

根据主定理有 $T(S)=O(S^\frac32\log S)$。

首先将所有方案中 $\vert\sum B_i\vert$ 和最大转化成 $\max(\sum B_i,-\sum B_i)$。

于是问题转化成了，每个点可以选择以 $B_i,-B_i,-A_i$ 计入贡献，对于之间有边的一对点 $(u,v)$，要么 $u$ 以 $-A_u$ 或 $v$ 以 $-A_v$ 计入贡献（被删掉），要么同时以 $B_u,B_v$ 或同时以 $-B_u,-B_v$ 计入贡献。

这是一个类似最大权独立集的问题。考虑转化为最小割模型，将点 $u$ 拆为 $u_+,u_-$，源 $S$ 向 $u_+$ 连边，$u_-$ 向汇 $T$ 连边。

源 $S$ 向 $u_+$ 的边不被割表示 $u$ 以 $B_u$ 计入贡献，$u_-$ 向 $T$ 的边不被割表示 $u$ 以 $-B_u$ 计入贡献，两条边都被割表示 $u$ 以 $-A_u$ 计入贡献。为了保证两条边不会都不被割，需要连边 $(u_+,u_-,+\infty)$；同理，对于之间有边的一对点 $(u,v)$，需要连边 $(u_+,v_-,+\infty)$ 和 $(u_-,v_+,+\infty)$。

对于某个点 $u$，设 $S$ 到 $u_+$ 的边权为 $x$，$u_-$ 到 $T$ 的边权为 $y$，$u$ 的贡献为 $z$ 减去最小割中连向 $u_+$ 的和从 $u_-$ 出发的容量，联立三种情况得

$$\displaylines{\begin{cases} z-y=B_u\\ z-x=-B_u\\ z-x-y=-A_u \end{cases} }$$

解得

$$\displaylines{\begin{cases} x=A_u+B_u\\ y=A_u-B_u\\ z=A_u \end{cases} }$$

求 $\max$ 式的最小值，首先二分答案，问题转化为单点修改，区间查询是否所有颜色都出现过。

二分后这个问题可以归约到三维数点，带上二分是 $O((n+q)\log^3(n+q))$ 的复杂度。

不过显然这个问题是比三维数点弱的，因为查询的是所有颜色是否都出现过，而非求颜色个数。沿用区间数颜色的记每个位置 $i$ 的上一次为该颜色的位置 $p_i$ 的想法，不难发现区间 $[l,r]$ 中所有颜色均出现，当且仅当对于所有颜色有 $p_i\le l$，其中 $i$ 为该颜色在 $r$ 之后第一次出现的位置（为了让每个颜色都出现，需要在序列末尾把每个颜色都添加一遍），当且仅当对于所有 $i>r$ 都有 $p_i\le l$。

所以用线段树维护后缀 $p_i$ 最小值，在线段树上二分即可做到 $O(q\log n)$。

如果存在一组匹配能够覆盖左部点集合 $X$，且存在一组匹配能覆盖右部点集合 $Y$，我们猜测 $X\cup Y$ 也能被一组匹配覆盖。

我们构造一个新图，对于原图上能覆盖 $X$ 的匹配中的一条边 $(u,v)$，我们在新图上连有向边 $(u,v)$；对于原图上 $Y$ 的匹配中的一条边 $(u,v)$，我们在新图上连有向边 $(u,v)$。不难发现新图上所有点的入度不超过 $1$。所以新图上的每个弱连通块都形如一条链或一个环。

对于原图上的一条极长链 $(u_0,u_1),(u_1,u_2),\cdots,(u_{k-1},u_k)$，我们不失一般性地假定 $u_{k-1}\in X$，那么显然 $u_k\not\in Y$，否则链不会在此终止。

如果 $k$ 是奇数，我们取 $(u_0,u_1),(u_2,u_3),\cdots,(u_{k-1},u_k)$ 作为一组匹配；如果 $k$ 是偶数，我们取 $(u_0,u_1),(u_2,u_3),\cdots,(u_{k-2},u_{k-1})$ 作为一组匹配。不难发现这样一定能覆盖该链上所有在 $X\cup Y$ 中的点。

环同理，交替选取构造匹配即可。

于是根据霍尔定理，两部分别状压判断即可。

fail 数上的子树更改或查询是易于维护的，而对一个字符串在 AC 自动机上经过的路径进行更改或查询只能暴力做。

所以如果直接把 CF547E 的做法用到这里来，区间询问拆成前缀，对每个前缀按顺序处理，fail 树上子树加，每个询问在 AC 自动机上暴力求和，时间复杂度为 $O(A\sum|s_i|+B\sum|s_{t_i}|)$。其中 $t_i$ 为第 $i$ 次询问的文本串，$A$ 为区间加的时间复杂度，$B$ 为单点查询的时间复杂度。注意式子中第一个 $\sum$ 是有约束的（不超过 $10^5$），而第二个没有。这样我们就获得了一个与文本串串长相关的暴力做法。

注意到第一个做法的问题在于遍历文本串的次数过多。如果选择每个文本串只进行一次遍历，对经过的所有点做 $O(1)$ 子树加（树上前缀和），然后依此处理该文本串相关的所有询问，这个做法的时间复杂度为 $O(\sum|s_{t_i}|+|t|\sum|s_i|)$，$t$ 为询问的文本串序列。

于是我们根号分治：对于长度不超过 $\sqrt{\sum|s_i|}$ 的串使用第一种算法，使用 $A=O(\sqrt n),B=O(1)$ 分块进行区间加单点查；否则使用第二种算法，此时 $|t|=O(\sqrt{\sum|s_i|})$。总时间复杂度为 $O((\sum|s_i|)^{1.5})$

中位数的性质是离不开它的排名的，所以常见的处理中位数最值的办法是二分答案。一个长为 $m$ 的序列中，（本题所定义的）中位数大于等于 $k$ 当且仅当小于 $k$ 的数的个数少于 $\left\lceil\frac m2\right\rceil$ 个。

于是这个问题就变成了，是否存在一个左端点在 $[a,b]$ 间，右端点在 $[c,d]$ 间，小于 $k$ 的数的个数少于某个与区间长度相关的值。

注意到此时限制是与区间长度相关的，难以对所有区间进行统一的处理。我们尝试对问题变形，设长为 $m$ 的区间中有 $t$ 个小于 $k$ 的数：

$$\displaylines{t<\left\lceil\frac m2\right\rceil\iff2t<m\iff(m-t)-t>0 }$$

此时式子的含义已经很明确了，中位数大于等于 $k$ 当且仅当区间中大于等于 $k$ 的数的个数减去区间中小于 $k$ 的数的个数大于 $0$。

于是可以用可持久化线段树维护，第 $i$ 个版本对应原序列中第 $i$ 小的数 $x$，线段树上某个位置小于 $x$ 赋为 $-1$，大于等于 $x$ 赋为 $1$，线段树上维护区间和、最大前缀和、最大后缀和，这样每个询问应对的所有区间的和的最大值可以通过线段树快速地求出。