云斗26省选计划记录

会是最后一次集训吗？？

图论

简单图论，flows，二分图

省选联考2021 图函数

注意到一个性质：对于 $f(u,G)$，枚举到 $v$，所有 $w>v$ 的 $w$ 才产生贡献。

Proof：假设存在一个 $w<v$，使得不同时存在 $u\to w\land w\to w$。若 $w$ 对 $u\to v\to u$ 有贡献，不妨设在 $u\to v$ 上。那么此时 $w$ 可以通过 $v\to u$ 再次回到，即存在贡献，矛盾。

考虑一对 $(u,v)$ 在什么时候对 $G_i$ 贡献，发现是 $u\to v\to u$ 路径上经过的路径上点编号大于 $v$，且最小边编号值大于 $i$ 时才有贡献。

于是设 $g_{i,j}$ 表示最大化的 $i\to j$ 路径上的最小边权。从大到小枚举 $k>j$，有 $g_{i,j}=\max\min (g_{i,k},g_{k,j})$，这是一个类似 Floyd 的转移。

然后就做完了。

[HNOI2019] 校园旅行

神仙题。

回文串具有性质：设 $s$ 为回文串，则 $\texttt{x}s\texttt{x}$ 仍然为回文串。

容易设计暴力，以点对 $(x,y)$ 为状态表示 $(x,y)$ 存在合法路径，枚举两点的连边。复杂度 $\mathcal O( (\sum\deg)^2)=\mathcal O(m^2)$。

由于可以多次走一条路径，考虑奇偶性的影响。保留连接颜色相同的点的边，对同色的连通块进行分讨。

• 对于为二分图的连通块，无论怎么走都不会改变长度的奇偶性。于是只需要保留连通块的一个生成树。
• 对于非二分图的连通块，那么可以改变长度奇偶性。保留连通块的一个生成树，然后随便选一个点加上自环（这样就形成奇环，每跑一遍都能改变奇偶性。）

接下来考虑异色连通块怎么搞。

由于异色，于是天然是二分图。直接保留一棵生成树即可。

综上，总边数降到了 $\mathcal O(n)$ 级别，复杂度进而达到了 $\mathcal O(n^2)$ 级别。

A

$u<v$ 转化成二分图上模型，左部点为边，右部点为 $T_1$ 中 $1\sim n-1$ 以及 $T_2$ 中 $2\sim n$ 中的点。

然后转化成完美匹配计数了。

[CEOI 2023] Balance

考虑 $S=2$ 的时候怎么做，相当于左右集合中任意元素出现次数差不超过 $1$。考虑设一行为一条无向边，相当于给边定向使得任意一点的出入度之差不超过 $1$。考虑欧拉回路，对于奇点与超级源点相连即可。

拓展到 $S=2^k$ 的做法。考虑将大问题划分成子问题，即将 $[1,2^k]$ 分割成 $[1,2^{k-1}],(2^{k-1},2^k]$ 两部分，进而划分出对于每个评测机，每个题目时间区间。通过欧拉回路，使得将每道题目尽量平均地分配到两个集合。

这样做对的本质是，不考虑相对顺序，将 $N$ 个数尽量均匀地分到 $2^k$ 个集合中，分出的最小数与最大数的差不超过 $1$。而每次的分治恰好就是实现了这样的过程，进而全局都是对的。

具体的实现，只要看当前点作为入点是否被划分到分治的对应区域即可。

QOJ3159 Sugar Glider

只需加上一个状态已经转移方案跑最短路即可。

QOJ15315 Hamu

给出大小为 $n$ 的无向图，每个城市的游览次数 $a_i$。构造访问次数不超过 $5n$ 的一种方案，从 $s$ 出发，最终回到 $s$，使得每个城市都被访问偶数次。特别的，首次在 $s$ 出发不算在访问次数内。

先把 $a_i\gets a_i\bmod 2$。于是问题变成了让你构造方案使得每个城市访问次数 $c_i\equiv a_i\pmod 2$。

若该图是个二分图，就全是偶环，那么 $\sum a_i\equiv 2\pmod 2$。不满足就非法。

若该图有奇环，可以先跑一个奇环，然后就使 $\sum a_i$ 又变成偶数了。这是为啥？你考虑从 $s$ 出发，跑一个奇环，再回到 $s$。划分成两部分，奇环上的点以及 $s$ 到奇环上 $t$ 的点。$nxt(s)$ 到 $t$ 都跑了两次，奇偶性没变，但是奇环上其他点以及 $s$ 的奇偶性变了，一共有奇数个变了，所以是对的。

下面尝试构造，先跑出原图的一个生成树。然后从 $s$ 出发，每次修正一下就行了。

UVA1083 Fare and Balanced

给出 DAG，给一些边权增大，使得任意一条 $1\to n$ 的路径长相等，且任意一条路径最多一条边被修改。报告无解或者一组解。

一种无解的情况就是，$1\to u$ 和 $u\to n$ 分别有不少于 $2$ 组值，两两组合有 $4$ 种情况（重复的话也有 $3$）种，对于一条路径至少修改两条边才行。

另外，修改越少越优，故先跑出原图的最长路，这个最长路就应该所有路径的最终长度，设这个长度为 $s$。

考虑一条边 $(u,v,w)$。若在 $1\to u$ 上存在两个值或者 $v\to n$ 上存在两个值或者已经修改过就不能修改。若能修改，即不存在上述情况，那么增加 $s-\operatorname{dis}{1,u}-\operatorname{dis}{v,n}-w$。

最后再跑一遍看看是不是符合条件即可，找不同路径可以用正反图最长短路实现。

[ARC115F]

最大最小可能值，考虑二分。

注意到操作可逆，于是将状态划分为等价类。只要一种状态既能从初始转移又能从末状态转移，那么该状态就是合法的。

P9760 [COCI 2022/2023 #3] Skrivača

首先注意到 Marin 必然要走到割点 $v$ 上，且上一步中 Luka 从 $a_u$ 走到 $a_v$，其中 $a_u$ 与 $a_v$ 被划分成两部分，可以用圆方树直接维护。特别的，当存在 $a_k=k$ 时，也要考虑一下该情况。走到这个点对就行，只要存在一个解，其他解必然都存在。

考虑在找到所有割点以及相邻点对，直接在树上找最近的就行了。

[QOJ14720]

抽象成 2-SAT 模型然后发现有平方级别的边。

随便做然后线段树优化即可。

AGC032C Three Circuits

注意到这个图本身必然是一个欧拉图，下文默认图为欧拉图。

另外，设 $d_i$ 表示点 $i$ 的度数。考虑一进一出，那么经过该点可以分出 $\dfrac d2$ 个回路，故只要存在点 $u$ 使得 $d_u\ge 6$，那么必然有解。

如果 $\max d_i=2$，那么显然只有一个环。若 $\max d_i=4$，考虑该点的个数：

如果只有一个 $d_i=4$，那么显然只有二回路。

如果有两个 $d_i=4$，实际上就是一个环上挂两个环这样的结构才有解。

如果有三个或者更多 $d_i=4$，必然存至少三回路。

P8215 [THUPC 2022 初赛] 分组作业

首先可以划分成 $S,T$ 集合，分别表示愿意或不愿意，即 $S\overset{d_i}{\longrightarrow} i\overset{c_i}{\longrightarrow} T$。

队友之间的贡献，即 $a\overset{e_a}{\longrightarrow} b$ 以及对称的。

考虑合作关系。考虑对于一对队友 $(2i-1,2i)$，建立虚点 $p_i$。$p_i\overset{\infty}{\longrightarrow}2i-1$ 以及 $p_i\overset{\infty}{\longrightarrow}2i$ 表示若 $p_i$ 在 $S$ 侧有流就必然使这对都愿意。

接下来考虑喜欢关系 $(A,B,a,b)$。若 $A$ 未合作且 $B$ 愿意，即 $B$ 在 $S$ 侧且 $p_A$ 在 $T$ 侧，产生 $a$ 的贡献，也就是 $B\overset{a}{\longrightarrow} p_A$。若 $A$ 不愿意但 $B$ 合作，也就是 $A\in T,p_B\in S$，就连 $p_B\overset{b}{\longrightarrow}A$。边数是 $8n+2m$.

数据结构

P4247 [清华集训 2012] 序列操作

设计 info 有 $F_i$，表示选 $i$ 个方案和的值，即 $F_i=\sum\limits_{T\subseteq S,\vert T\vert=i}\prod\limits_{j\in T}j$。tag 为 add 与 inv，表示懒惰加与懒惰取反。

取反操作是容易的，考虑区间加。

$$ \begin{aligned} F_i’ &= \sum\limits_{T\subseteq S,|T|=i}\prod\limits_{j\in T}(j+k) \\ &= \sum\limits_{T\subseteq S,|T|=i}\sum\limits_{p=0}^i k^p \sum\limits_{U\subseteq T,|U| =i-p}\prod\limits_{j\in U}j \\ &= \sum\limits_{p=0}^i k^p \sum\limits_{T\subseteq S,|T|=i}\sum\limits_{U\subseteq T,|U|=i-p}\prod\limits_{j\in U}j \end{aligned} $$

实际上这对每一个 $S$ 不超过 $i$ 的子集做了多次运算。考虑长度为 $i-p$ 的一个子集 $P$ 被选了多少次，即在 $S\setminus P$ 中选 $p$ 个，即 $\dbinom{|S| -i+p}{p}$。故有：

$$ F’_i = \sum_{p=0}^i \dbinom{|S|-i+p}{p} k^p F_{i-p} $$

可以直接 $\mathcal O(k)$ 转移。

对于合并 info，实际上就是一个卷积。由于 $\max k\le 400$，随便转移。

SPOJ - GSS2 Can you answer these queries II

转化一下，设 $a_i$ 上一次出现的位置是 $pre_{a_i}$，将一个子段 $[l,r]$ 视为平面上的点 $(l,r)$。一次查询 $(u,v)$ 相当与查询矩形区域 $[u,v]\times[u,v]$ 的最大点值。对于一个元素 $a_i$，贡献到 $(pre_{a_i},i]\times[i,n]$ 这个矩形。

然后就可以随便做了。

离线的话，设 $f_i$ 表示以 $i$ 为左端点的子段最大和，以及 $g_i$ 表示到当前最右侧的子段和。对于新的 $r$，对 $(pre_{a_r},r]$ 执行 $g_i\gets g_i+a_i,f_i\gets \max(f_i,g_i)$ 即可。

P3991 [BJOI2017] 喷式水战改

套路题。

考虑不带修怎么做。

设 $f_{i,k}\quad(0\le k\le 3)$ 表示到第 $i$ 个选择第 $k$ 个状态的最大值，$A_{i,k}=\begin{cases} a_i,&k=0\lor k=3 \\ b_i,&k=1, \\ c_i,&k=2 \end{cases}$ 有转移：$f_{i,k}=\max_{j\le k}f_{i,j}$。

转成矩阵的形式，上式可表述为：

$$\begin{bmatrix}f_{i,0}&f_{i,1}&f_{i,2}&f_{i,3}\end{bmatrix}=\begin{bmatrix}f_{i-1,0}&f_{i-1,1}&f_{i-1,2}&f_{i-1,3}\end{bmatrix}\begin{bmatrix}A_{i,0}&A_{i,1}&A_{i,2}&A_{i,3}\\-\infty&A_{i,1}&A_{i,2}&A_{i,3}\\-\infty&-\infty&A_{i,2}&A_{i,3}\\-\infty&-\infty&-\infty&A_{i,3}\end{bmatrix}$$

设 $\boldsymbol{F_i}=\begin{bmatrix}f_{i,0}&f_{i,1}&f_{i,2}&f_{i,3}\end{bmatrix}$，$\boldsymbol{M_i}=\begin{bmatrix}A_{i,0}&A_{i,1}&A_{i,2}&A_{i,3}\\-\infty&A_{i,1}&A_{i,2}&A_{i,3}\\-\infty&-\infty&A_{i,2}&A_{i,3}\\-\infty&-\infty&-\infty&A_{i,3}\end{bmatrix}$，这里的 $\boldsymbol{F_0}=\begin{bmatrix}0&0&0&0\end{bmatrix}$ 。根据矩阵的结合律，所求即为 $\max\left(\boldsymbol{F_0}\times\prod\limits_{i=1}^n\boldsymbol{M_i}\right)$。

维护矩阵积即可，随便用平衡树怎么维护都可以。

P3103 [USACO14FEB] Airplane Boarding G

这也太难了。

给出数轴上 $n$ 头奶牛。第 $i$ 头奶牛初始在点 $i-n$ 上。第 $i$ 头奶牛希望走到 $S_i$ 上，并花费 $T_i$ 的时间放行李，放完后会坐下。对于在其后的奶牛，需要等待其坐下之后才可继续走。求所有奶牛坐下的时间。

显然只有 $j>i$ 的奶牛 $j$ 对奶牛 $i$ 可能有影响，故倒序考虑奶牛。设 $ans_i$ 表示 $i$ 奶牛在 $ans_i$ 时刻才能坐上座位。

考虑维护限制集合 $F=(a,t)$ 表示到达 $a$ 时刻至少为 $t$。这样对于新的奶牛，容易找到其答案 $ans_i=\max\limits_{(a,t)\in F\land a\le  S_i}(S_i-a+t)+T_i$，只和 $t-a$ 有关。初始时，令 $F={(0,0)}$。

考虑对于新的奶牛 $i$，如何进一步地维护该集合。注意到 $(S_i,ans_i+1)$ 实际上符合 $F$ 集合的定义，即后面的奶牛要走到 $S_i$，至少让他坐在座位上才可以。另外，奶牛 $i$ 必然在满足 $a\le S_i$ 的所有 $(a,t)$ 限制时排队，即在 $t$ 时才从 $a-1$ 离开到达 $a$。于是对于所有这样的限制 $(a,t)\gets (a-1,t)$。

具体而言，只需维护一个集合 $F$。对于新奶牛 $i$，计算出 $\max\limits_{(a,t)\in F\land a\le S_i} (v-a)+S_i+T_i$ 并赋值给 $ans_i$，之后对修改后的集合中所有满足 $a\le S_i$ 的 $(a,t)$ 执行 $(a,t)\gets (a-1,t)$，最后向 $F$ 加入限制 $(S_i,ans_i+1)$ 即可。

综上，我们需要一个查找区间最值，动态插入，前缀坐标平移的数据结构。平衡树维护即可。

对于被二维偏序的（即 $a_i<a_j\land t_j-a_j<t_i-a_i$ 的 $j$ 者），直接删掉。这样维护的便是前缀最大值的集合，这一步可以只是优化写法，可以略去。

P4577 [FJOI2018] 领导集团问题

人话题意：给出树，点有权 $w_i$。求最大子集使得对于集合内任意有祖孙关系两点 $u\in subtree(v)$，都有 $w_u\ge w_v$。

$n\le 2\times 10^5$。

设 $f_{i,j}$ 表示在子树 $i$ 中，选的最小的值至少为 $j$ 的最大集合大小。容易设计转移：

$$\begin{cases} f_{u,j}\gets 1+\sum\limits_{v\in son(u)}f_{v,w_u}, &u\text{ is chosen and }j\le w_u, \\ f_{u,j}\gets \sum\limits_{v\in son(u)}f_{v,j},&u\text{ is not chosen}. \end{cases}$$

容易取前缀最大值且离散化优化为 $\mathcal O(n^2)$。

考虑进一步优化，注意到一个节点至多会贡献一个新状态，且一个节点只能唯一地向父节点传递，因此直接用线段树合并即可。

但是你发现朴素的合并会涉及到线段树合并加上区间修改，复杂度会爆炸，这是由于 merge 时会下传标记。注意到只要存在推平标记，相当于给另一棵树打上整体加标记，于是再维护一个整体加就能保证复杂度是对的。

另一种做法就是对 $f$ 差分。

细看一下 merge 部分吧。

另外一种做法就是设 $f_{u,i}$ 表示从 $\operatorname{subtree}(u)$ 中选 $i$ 个点的最小那个，维护多重集，启发式合并，十分好写。

P6773 [NOI2020] 命运

给出树 $T=(V,E)$，有限制集合 $S=V\times V$，对于任一组 $(u,v)\in S$，$u,v$ 有祖孙关系。给边染黑白色，使 $S$ 中任意一组 $(u,v)$，$u\to v$ 路径上的边至少有一条黑边，求方案数。

考虑先写一个朴素的多项式做法。设 $f_{u,o/1}$ 表示分配好 $\operatorname(u)$ 内的所有边且子树内限制均合法，不存在/存在 $y\in \operatorname{subtree}(u)\land u\in\operatorname{subtree}(x)$ 的限制没被满足的方案数。考虑从子节点 $v$ 向父节点 $u$ 如何转移。发现处理 $x=u$ 的限制时对于 $f_{v,0}\to f_{u,0}$ 无法转移。

考虑记录 $d$ 表示最深的 $x$ 的深度，$f_{u,d}$ 定义亦如此。特别的，$d=0$ 时表示全部满足。增设 $g_{u,i}$ 表示限制深度至多为 $i$ 的方案数。讨论 $v\to u$ 边的颜色。

染黑。

$$f_{u,d}\gets f_{u,d}g_{v,dep_u}$$

染白。

考虑当前的 $d$ 由 $u$ 还是 $v$ 贡献，有

$$f_{u,d}\gets f_{u,d}g_{v,d} + g_{u,d-1}f_{v,d}$$

综上，有转移式：

$$f_{u,d}\gets f_{u,d}(g_{v,dep_u}+g_{v,d})+f_{v,d}g_{u,d-1}$$

注意到，一次新增的状态只有 $dep_u$。故合并即可，

看一下 dfs 与 merge 函数的逻辑。

P9336 [Ynoi2001] 梦想歌

定义集合合并顺序：权值和不同则从小向大合并，相同则深度更大的向小的合并。在树上从底向上合并集合，假设某个点 $x$ 的子树全部合并完毕，以 $x$ 为初始集合，按照子节点编号从小到大排序后合并，每个点初始视为一个集合。多次查询，修改某个点的权值，或者询问某个子树内不会被并入其他集合的点权。

$n,q\le 2\times 10^5$。

先考虑暴力怎么写。每次修改权值后直接重构，按照顺序枚举后直接递推，容易做到 $\mathcal O(nq)$。

P3309 [SDOI2014] 向量集

在线维护向量集合。每次可以查询插入顺序在 $[l,r]$ 范围内与 $(a,b)$ 点积最大的向量，或者插入新的向量。

每次询问为 $(x,y)\in S[l,r]$ 的 $\max b(\dfrac ab x+y)$，考虑如何最大化 $f(x)=\dfrac abx+y$。

设 $-\dfrac ab=k$，则 $y=kx+f(x)$，于是 $f(x)$ 即为这个函数的纵截距。考虑用斜率为 $k=-\dfrac ab$ 的直线去截点集，纵截距最大者即所求。另外这显然答案只会在凸包上的。

二分斜率，找到相邻三点斜率包含 $k$ 的中间点即所求。

下面的问题就是如何维护凸包呢，考虑倍增地维护每个区间长。就是用线段树维护凸包。具体来说，由于不涉及修改，每个节点在被填满后再维护一下凸包，复杂度是 $\mathcal O(len)$ 的（归并），没被填满就不维护（由于查的都是插入过的，因此不会出现被完全覆盖的点没被维护凸包的情况）。对于查询，在每个被完全覆盖的点二分一下就好。

唉唉上面写的好像有点麻烦。你注意到答案一定在凸包上，然后因此答案是单峰的，考虑三分也行？

P8987 [北大集训 2021] 简单数据结构

给出序列 $a$，$q$ 次操作：

1. 全局 $a_i\gets \min(a_i,v)$。
2. 全局 $a_i\gets a_i+i$。
3. 查询 $\sum\limits_{i=l}^ra_i$。

$n,q\le2\times10^5$。

假设 $a$ 不降，那么显然在任意操作后 $a$ 仍然不降。于是考虑将 $a$ 划分成两类，一类是不降的子集合 $S$ 以及剩下的 $T=[1,n]\setminus S$。其中 $S$ 集合可以用带懒标记的线段树二分实现。

另外，如有新的元素被执行 1 操作，那么该元素应直接插入 $S$ 且仍不降。

这是由于在执行操作 $1$ 后，$S$ 中小于 $v$ 的不变，剩下一段后缀被推平。当某个元素 $i$ 被插入时，必然在推平的后缀的某个位置上。假设存在 $(j,a_j)\in S$ 使得新元素 $i<j\land a_j<v$，则 $a_j$ 在加入 $S$ 时刻必然大于 $a_i$，该时刻 $a_i<a_j\land i<j$，根据前面的结论说明此后都有 $a_i\le a_j$，与 $a_j<v\le a_i$ 矛盾。

根据上述性质，我们只需分别维护 $S,T$ 的区间和即可。

考虑如何快速地把 $T$ 中元素删除并插入到 $S$ 中。设 $t_i$ 表示第 $i$ 个元素被挪到 $S$ 中的时间（第几个操作），$p_i$ 表示截止操作 $i$ 执行了操作 2 的次数。则 $t_i$ 满足 $a_i+p_{t_i}\cdot i\ge v_{t_i}$，变形一下就是 $i\cdot p_{t_i}+a_i-v_{t_i}\ge 0$，用可持久化李超树维护函数 $y=p_{t_i}x-v_{t_i}$ 的全局最值（或者整体二分套一下）即可，在上面二分可以做到 $\mathcal O(n\log ^2n)$。

进一步的，注意到 $p_{i}$ 单调不降，用整体二分求凸包后双指针就能做到 $\mathcal O(n\log n)$，注意一下对于同横坐标点的特判。

在线的话好像要用 KTT，不会捏/kk。

P8264 [Ynoi Easy Round 2020] TEST_100

给定一个长为 $n$ 的序列 $a$，每个位置是一个变换 $x=|x-a_i|$，每次查询给出一个区间 $[l,r]$ 和一个值 $v$，依次令 $i$ 从 $l$ 到 $r$ ，访问每个元素 $a_i$，将 $v$ 变为 $|v-a_i|$，求结束后的 $v$ 的值。

$n,m,a_i,v\le 10^5$。

注意到每次操作后，值域仍然为 $[0,10^5]$。考虑对每个块，预处理出 $f_{i}$ 表示 $i$ 经过块的变换后的值。

初始时 $f_v=v$，对于块的新操作 $a_i$。把 $f_v<a_i$ 视作 $-f_v+a_i$，把 $f_v\ge a_i$ 的视作 $f_v-a_i$。你发现这就是第二分块，我们希望维护一个块的复杂度只与值域有关，考虑延续第二分块的做法，用并查集维护。

那么分别考虑块内最值，设当前最大值为 $A$，最小值为 $B$，对于一次操作 $a_i$：

• 若 $a_i-A<B-a_i$，考虑将 $v\in [A,a_i]$ 都连边 $(f_{v},f_{2a_i-v})$，再打个全体 $-a_i$ 的标记。需要处理的值域大小减小了 $a_i-A$。
• 若 $a_i-A\ge B-a_i$，考虑将 $v\in [a_i,B]$ 连边 $(f_v,f_{2a_i-v})$，打个全体 $\times -1+t$ 的标记。需要处理的值域大小减小了 $B-a_i$。

另外，每次的 $a_i$ 如果与 $[B,A]$ 无交，那么可以直接特判后打标记，无需进行并查集的连接操作。

注意到每个值都仅进行了一次主动连边操作，因此一个块的复杂度是 $\mathcal O(V\alpha (V))$，后面并查集的复杂度可以看作常系数。总复杂度为 $\mathcal O( (n+m) \sqrt n)$。> 给定一个长为 $n$ 的序列 $a$，每个位置是一个变换 $x=|x-a_i|$，每次查询给出一个区间 $[l,r]$ 和一个值 $v$，依次令 $i$ 从 $l$ 到 $r$ ，访问每个元素 $a_i$，将 $v$ 变为 $|v-a_i|$，求结束后的 $v$ 的值。

$n,m,a_i,v\le 10^5$。

注意到每次操作后，值域仍然为 $[0,10^5]$。考虑对每个块，预处理出 $f_{i}$ 表示 $i$ 经过块的变换后的值。

初始时 $f_v=v$，对于块的新操作 $a_i$。把 $f_v<a_i$ 视作 $-f_v+a_i$，把 $f_v\ge a_i$ 的视作 $f_v-a_i$。你发现这就是第二分块，我们希望维护一个块的复杂度只与值域有关，考虑延续第二分块的做法，用并查集维护。

那么分别考虑块内最值，设当前最大值为 $A$，最小值为 $B$，对于一次操作 $a_i$：

• 若 $a_i-B<A-a_i$，考虑将 $v\in [B,a_i]$ 都连边 $(f_{v},f_{2a_i-v})$，再打个全体 $-a_i$ 的标记。需要处理的值域大小减小了 $a_i-B$。
• 若 $a_i-B\ge A-a_i$，考虑将 $v\in [a_i,A]$ 连边 $(f_v,f_{2a_i-v})$，打个全体 $\times -1+a_i$ 的标记。需要处理的值域大小减小了 $A-a_i$。

另外，每次的 $a_i$ 如果与 $[B,A]$ 无交，那么可以直接特判后打标记，无需进行并查集的连接操作。

注意到每个值都仅进行了一次主动连边操作，因此一个块的复杂度是 $\mathcal O(V\alpha (V))$，后面并查集的复杂度可以看作常系数。设 $n,m,V$ 同阶，总复杂度为 $\mathcal O(n\sqrt n)$。

对于上述问题的具体实现可以将操作 $a_i$ 视作折痕，一次操作相当于将数轴以 $a_i$ 为轴对称。分别对乘法标记的正负以及对折方向这些情况具体分析即可。

P8339 [AHOI2022] 钥匙

给出树，点有宝箱或者钥匙。宝箱钥匙有色，对应颜色的钥匙只能开对应颜色的宝箱，开完废弃，且同色钥匙至多五个。多次询问求 $u\to v$ 路径上可以开多少宝箱，询问独立。

$n\le5\times 10^5,q\le 10^6$。

颜色之间相互独立，考虑分别对每种颜色操作。

对每个颜色建虚树。该颜色内，考虑一把钥匙对其他宝箱的贡献，可以直接暴力枚举这样的对，对数为该色钥匙数量与宝箱数量乘积，求和总复杂度即为 $\mathcal O(5n)=\mathcal O(n)$。

假设一只钥匙宝箱点对 $(u,v)$，考虑如何统计贡献。直接分类讨论再把这个拍到 dfs 序上，就转化成二维平面问题了，详见 Tricks 的第 24 点。

实际上可以不建虚树，直接统计，呃那好像要分块一下，有点麻烦，还是建虚树吧。

求虚树时，LCA 要用欧拉序 $\mathcal O(1)$ 求，否则跑不过去。。

P5926 [JSOI2009] 面试的考验

求区间最接近且不相等的两数之差的绝对值。

先考虑 $i<j,a_i<a_j$ 的贡献。

固定 $i$，设 $j$ 为最小的满足 $a_j>a_i\land j>i$ 的数，$j$ 会产生贡献。

考虑下一个产生贡献的数，必须满足 $a_k-a_i<a_j-a_i\land a_k-a_i\le a_j-a_k$，得到 $a_k$ 的值域为 $\left(a_i,\dfrac {a_i+a_j}2\right)$。也就是说，每次找下一个产生贡献的数，值域减半。对于 $i<j\land a_i>a_j$ 的情况做相似的处理。于是即可在 $\mathcal O(\log V)$ 的时间内处理完一个位置的贡献。

然后随便维护二维数点就做完了。

P8330 [ZJOI2022] 众数

给出序列 $a$，找子区间 $[l,r]$，使得 $[l,r]$ 众数出现次数与 $[1,l)\cup(r,n]$ 内众数出现次数最大。输出这个最大次数，并输出外区间的所有众数。

$n\le 2\times 10^5$。

处理众数相关问题肯定不能 polylog，考虑根号相关。这里有出现次数的分类，故考虑根号分治。把序列中出现次数 $\ge B$ 的数称为 A 类，出现次数 $<B$ 的数称为 B 类。这样，使 A 类数的种类不超过 $\dfrac nB$，B 类数的出现次数不超过 $B$，下取 $B=\sqrt n$。

若子区间 $[l,r]$ 或者外区间 $[1,l)\cup(r,n]$ 存在 A 类数，分类讨论：

• 若外区间存在，设 A 类在子区间内出现次数为 $y$，枚举所有其他色，设枚举色 $i$ 出现次数为 $x$。最大化 $x-y$ 即可。注意到所有有贡献的点必然为色 $i$ 所在点，因此复杂度可以控制在 $\mathcal O(n\sqrt n)$。
• 若内区间存在，可以通过循环移位的方式转化为上述情况，本质相同，故仍可通过上述方法进行。

若不存在 A 类作为众数，即子区间与外区间众数均为 B 类。考虑求出 $f_{r,k}$ 表示最大的 $l$ 使得 $[l,r]$ 的众数出现次数为 $k$。枚举每个 B 类数，处理前缀和后再枚举为该数的位置，复杂度为 $\mathcal O(n\sqrt n)$。对于 $f_{r,k}$，由于该情况处理的均为 B 类，因此直接枚举 B 类向前跑然后取前缀 $\max$ 即可。

P5631 最小mex生成树

一种朴素的方法是，枚举每个作为 mex，看是否可行。复杂度是 $\mathcal O(mw\alpha (n))$ 的。

考虑线段树分治，设分治区间 $[l,r]$ 表示不含边权其中的图。用可撤销并查集维护就完了。复杂度是 $\mathcal O(m\log n\log w)$。

P7708 「Wdsr-2.7」八云蓝自动机 Ⅰ

给出序列 $a$，可以进行单点赋值，交换两个值，查询值操作。给出该操作序列 $B$，并有多次询问 $[l,r]$，表示在进行 $i\in[l,r]$ 中的 $B_i$ 操作后查询操作之和，各查询相互独立。

单点赋值 $a_i\gets k$ 不好写，可以视作在序列末尾再塞一个元素 $a_{n+1}=k$，然后交换。

考虑莫队。在此讨论一下交换的性质：

• 若向左拓展 $[l,r]\to[l-1,r]$ 的是交换操作 $(i,j)$。受到影响的应为交换后最终映射到原序列上 $a_i,a_j$ 的数。设 $a’i=a{b_i}$，其中 $a’$ 是交换后的序列，$a$ 为原始序列。只需交换 $b_x=i,b_y=j$ 的 $b_x,b_y$ 即可，额外维护 $c_i=k$ 表示 $b_k=i$，同时更新。
• 若向右拓展 $[l,r]\to[l,r+1]$ 的是交换操作 $(i,j)$。受到影响的应为 $a’$ 序列的 $a’_i,a’_j$，直接交换 $b_i,b_j$ 以及对于的 $c$ 即可。

撤销相当于再次进行了该操作，承接上述操作即可。新增的查询操作也较为简单。

另外，考虑以上拓展操作对已有查询的影响。注意到实际上难以维护直接 $a’_i$，用 $b_i$ 的映射方式维护更优。设 $t_i$ 表示 $b_i$ 被询问的次数，

• 向左拓展，新增交换 $(i,j)$ 的影响。考虑维护 $t_i$ 表示 $a_i$ 被查了多少次，将答案对应更新：$ans\gets ans-t_i\cdot a_{i}-t_j\cdot a_{j}+ t_j\cdot a_{i}+t_i\cdot a_{j}$，后直接交换 $(t_i,t_j)$；
• 向右拓展，新增交换 $(i,j)$ 的影响。对答案没有实质影响，只用进行上述交换即可。

查询的话直接更新对应的 $t_i$ 以及 $ans$ 即可。

CF555C Case of Chocolate

注意到一次操作相当于截断，如从 $(x,y)$ 进行向上操作，设上边界为 $x=a$，那么这一次操作就相当于对 $i\in [x,a)$ 的所有向左更新最右边界。然后随便做。

CF1004F Sonya and Bitwise OR

一个 trivial 的想法是分治，确定中间节点后 two-pointer 做，容易做到 $\mathcal O(N\log N)$

注意到一个优秀的性质，即前后缀的 OR 和至多有 $\mathcal O(\log a)$ 种，这是因为每次按位或操作至多会增加一位。于是分治的复杂度就变成 $\mathcal O(\log N\log a)$ 了。

实际上线段树就是分治结构。设 $f(l,r)$ 表示合法的 $[L,R]\subseteq[l,r]$ 的对数，然后 pushup 函数实际上就是上述的操作，随便做？

CF1217F Forced Online Queries Problem

给出 $n$ 个点的图。$m$ 次操作，每次将 $(u,v)$ 边存在状态取反或者查询连通性，初始边都不存在。特别的，有加密状态，设上一次连通状态为 $lst=1/0$，则当前 $u’\gets (u+lst-1)\bmod n+1,v’\gets (v+lst-1)\bmod n+1$。

乍一看是线段树分治模板题，但是发现有强制在线？

仔细想一下其实强制在线是假的，因为每次只有两种情况。由于线段树分治是半在线的，即遍历每个叶子节点是按时间顺序的，因此在遍历到某个叶子时可以知道其存在状态。

于是就有简单想法，查询操作是容易的，考虑修改操作。假设当前时间为 $t$，得到当前实际修改边 $(u,v)$ 后。若从不存在改变为存在，则对 $(t,nxt_{u,v}-1)$ 进行修改操作（其中 $nxt_{u,v}$ 是下一次可能的修改该边操作时间，也就是普通线段树分治的 modify 操作），并更新 exist[u,v] 的状态。从存在改为不存在直接更新 exist[u,v] 即可。对 $1-lst$ 的边也要操作，若当前存在状态为真，那么要延续操作，即再 modify 一次即可。

CF1824D LuoTianyi and the Function

给出 $a$。设 $g(i,j)$ 表示最大的 $k$ 使得 $x\in[i,j]$ 的所有 $a_x$ 都在 $y\in[k,j]$ 的 $a_y$ 中出现过。特别的，当 $i>j$ 时，$g(i,j)=0$。多次询问，给出 $(l,r,x,y)$，每次查询 $\sum\limits_{i=l}^r\sum\limits_{j=x}^y g(i,j)$。

若固定 $r$，求一段 $\sum\limits_{x}g(x,r)$ 用扫描线维护是容易的。也就是对于固定的 $r$，对 $nxt_{a_i}>r$ 的位置 $i$ 戳成 $1$，反之戳成 $0$。$r$ 每加 $1$，影响到的仅有与 $a_r$ 相同的位置，设这个位置为 $k$，增设 $k$ 前面的 $1$ 的位置为 $l$。对 $(l+1,k)$ 区间赋值即可。对于 $1$ 的维护可以直接用 set。

然后你发现这个东西实际上能前缀和维护，即

$$\sum\limits_{i=l}^r\sum\limits_{j=x}^yg(i,j)=\sum\limits_{i=l}^r\sum\limits_{j=1}^yg(i,j)-\sum\limits_{i=l}^r\sum\limits_{j=1}^{x-1}g(i,j)$$

于是只需要对于每个 $l$，用矩阵维护历史和即可。但是要卡常，所以把矩阵展开来就好。

$$\sum\limits_{i=l}^r\sum\limits_{j=x}^yg(i,j)=\sum\limits_{i=l}^r\sum\limits_{j=1}^yg(i,j)-\sum\limits_{i=l}^r\sum\limits_{j=1}^{x-1}g(i,j)$$

于是只需要对于每个 $l$，维护历史和即可。注意对于没有影响的每次不能暴力加，直接维护一个 $tag$ 表示用了当前答案多久，然后被修改时再加到 $sum$ 里。

CF1866K Keen Tree Calculation

注意到答案一定是原树直径或者经过该点的最长链。

考虑如何求过该点的最长链，实际上就是最长加上次长。最长的话可以用李超树维护，然后次长可持久化一下查询即可。

CF702F T-Shirts

先以质量为第一关键字，价格为第二关键字排序一下。从前往后枚举，容易得到 $\mathcal O(nk)$。

进一步分析一下这个过程，实际上是对一些数 $v_1,v_2,\cdots,v_k$，进行 $n$ 次操作。每次操作若 $v\ge c_i$，则 $v\gets v-c_i$，并求这个操作次数。

用平衡树来维护 $v_i$，每次就是按照 $c_i$ 分裂，然后再对分裂出 $\ge c_i$ 的部分值集体 $-c_i$ 并给 $ans$ 打上 $+1$。

这里进行势能分析，注意到实际上有交的部分是值域在 $[c_i,2c_i)$ 的部分，故每次有交的值域都会减半。每个数至多会减半 $\log V$ 次，故合并的复杂度为 $\mathcal O(n\log n\log V)$。尝试暴力插入即可。

好像启发式合并也可以，但是常数很大。

CF1056G Take Metro

CF1479D Odd Mineral Resource

随机赋值，那么相当于在 $u\to v$ 路径上找异或值为正的，然后主席树上二分做完了。

CF1290E Cartesian Tree

根据笛卡尔树的性质，所求相当于每个位置作为最大值所在极大区间 $[l_i,r_i]$ 的长度和。

每次插入的一定是序列的最大值，因此影响到的是 $i\in [1,a_{n+1})$ 的所有 $r_i$ 以及 $j\in (a_{n+1},n+1]$ 的所有 $l_i$，有：

$$ \begin{cases} r_{i}\gets\min(r_i,a_{n+1}),&i\in[1,a_{n+1}) \\ l_{i}\gets\max(l_i,a_{n+1}),&i\in(a_{n+1},n+1] \end{cases} $$

然后对 $r_i$ 与 $l_i$ 分别求和，这就是 SegBeats 板子了。

CF981G Magic multisets

考虑对每个颜色独立维护出存在的区间，用 ODT 维护。但是 ODT 不优雅，用并查集。

P5327 [ZJOI2019] 语言

答案就是每个点能到达其他点个数之和的一半。

全局维护一个集合 $S={V\times V}$，枚举到 $u$ 时表示有多少路径要经过该点。仿照 雨天的尾巴 的 Trick，对于一条路径 $u\to v$，就在 $u,v,\operatorname{lca}(u,v),\operatorname{fa}(\operatorname{lca}(u,v))$ 分别打上 $1,1,-1,-1$ 的 tag，$1$ 表示加入路径点对，$-1$ 表示删除。

另外一个 Trick 就是，对于点集 $V’\subseteq V$ 形成的生成树的路径并大小为按照 dfs 序排序后，$\sum\limits_{i=1}^{\vert V’\vert}\operatorname{dis}(V’i,V’{i+1})$ 的一半，其中 $V’_{\vert V’\vert+1}=V’_1$。

然后启发式合并维护一下，就能做了？

还有一种做法就是用树剖将链划分成 $\log $ 段，然后再用线段树 $\mathcal O(\log n)$ 打上，最后扫描线，似乎是 3log，当年的机子反正跑不动。

字符串

P3546 [POI 2012] PRE-Prefixuffix

求给出串的最长相同的同构前后缀。

注意到这个前后缀同构相同，相当于：$AB\sim BA$。

考虑枚举 $A$ 的长度 $i$，然后要求的就是 $S[i+1,n-i]$ 的长度不超过 $\dfrac{n-2i}{2}$ 最长 Border，设这个值为 $f_i$。

同时维护 $(l,r)$ 表示 $B$ 的匹配是 $S[i+1,l]$ 与 $S[r,n-i]$。若 $f_i$ 较 $f_{i+1}$ 有增长，显然至多会增长 $2$ 个单位，即 $f_i\le f_{i+1}+2$。可以暴力维护，复杂度是线性的。

P12736 [POI 2016 R2] 圣诞灯链 Christmas chain

$n$ 条灯带，$m$ 个限制：$(a,b,t)$ 表示 $(a,b),(a+1,b+1),\cdots,(a+t-1,b+t-1)$ 灯带的颜色相同。求最多的颜色数。

朴素的并查集复杂度是 $\mathcal O(nm\cdot\alpha(n))$ 的，考虑优化。

注意到每次操作都是对连续区间的，因此考虑类似线段树优化建图的方法来优化并查集的合并。

具体的，尝试用倍增维护并查集。设 $fa_{i,j}$ 表示 $[j,j+2^i)$ 中被合并到别的区间上的左端点。例如 $[i,\cdots,i+2^k)$ 与 $[j,\cdots,j+2^k)$ 颜色分别对应，则 $fa_{k,i}=j$。对于非二的整次幂区间，从大到小分解即可。

继续考虑 $fa_{i,j}\to fa_{i-1,j}$ 的转移，实际上就是分别对 $fa_{i-1,fa_{i,j}}$ 位置与 $fa_{i-1,j}$ 与后半区间的合并，分别合并即可。

复杂度为 $\mathcal O(n\log n\cdot\alpha (n))$。

代码十分好写。

另一种解法是注意到至多有 $\mathcal O(n)$ 次合并，然后线段树维护哈希二分加上启发式合并做到的是 2log。

P3449 [POI 2006] PAL-Palindromes

给出回文串集合 $S$，求任意两两组合（可以与自己）后，回文的新串个数。

呃呃，随便分析一下就做完了。

QOJ6842 Popcount Words

有一个无限长的 01 串 $s$，第 $i$ 位为 $s_i=\operatorname{popcnt}(i)\bmod 2$。

给你 $n$ 个区间 $[l_i,r_i]$，定义 $S=s[l_1,r_1]+s[l_2,r_2]+\cdots+s[l_n,r_n]$。

q$ 次询问，每次给你一个 01 串 $T$，求 $T$ 在 $S$ 中的出现次数。

$1\le n,q\le 10^5$，$1\le \sum |T|\le 5\times 10^5$，$1\le l_i\le r_i\le 10^9$。

发现 $s$ 有很强的对称性。具体来说，设 $S_{i,0}=s[0,2^i-1]$，$S_{i,1}=[2^i,2^{i+1}-1]$，那么有 $S_{i,j}=S_{i-1,j}+S_{i-1,1-j}$，于是即可倍增。

对 $T$ 建出 ACAM 后，

P4548 [CTSC2006] 歌唱王国

给出长度为 $m$ 的序列 $a_i$，每秒会随机生成范围在 $[1,n]$ 的数放在另一个序列末尾。求生成的序列中连续完全包含序列 $a_i$ 的期望秒数。多测。

设 $I(i)$ 表示匹配到第 $i$ 位，当 $I(i)\to I(i+1)$ 时，设该期望值为 $E_i$。根据 P6835 的套路，期望的线性性，所求即为 $\sum\limits_{i=0}^{m-1} E_i$。

于是容易得到朴素的递推，设 $S_i$ 为 $E_i$ 的前缀和，有 $E_i=\dfrac1n\left(1+\sum\limits_{(i,j)}(1+S_i-S_{j-1})\right)$，化简一下就是 $E_i=n+(n-1)S_{i-1}-\sum\limits_{(i,j)}S_{j-1}$。考虑直接维护 $S_i$，有 $S_i=n(1+S_{i-1})-\sum\limits_{(i,j)}S_{j-1}$。设 $F_i=\sum\limits_{(i,j)}S_{j-1}$，有 $S_i=n(1+S_{i-1})-F_i$。

考虑怎么求 $F_i$，即考虑 $(i,j)$ 的分布。可以简单地 $\mathcal O(n)$ 地枚举下一位置的数，但太慢了。注意到有效贡献是失配树上 $i$ 到根的所有节点（且下一位均不同），然后就可以直接做了。

具体来说可以先从 $g_{fa}$ 保留贡献，然后再减掉祖先中下一位和自己这一位相同的贡献。

P5840 [COCI 2014/2015 #5] Divljak

给出字符串集合 $S$，多次操作。每次可以向 $T$ 插入串 $t$，或者有多少 $t\in T$ 包含 $s_x\in S$。

考虑对 $S$ 建 AC 自动机，建完后再建 fail 树。一次操作，相当于在 fail 树上，对所有被匹配到的点到根的路径并加一。但是你发现这个很难处理。

考虑一个关于 dfs 序的 Trick：对一组点 $p_1,p_2,\cdots,p_k$ 到根的并统一操作，相当于按照 dfs 序排序后，对 $i\in[1,k]$ 进行链修改（这里是到根进行 $+1$），对 $i\in[1,k)$ 的 $\operatorname{lca}(p_i,p_{i+1})$ 进行链修改（这里是到根进行 $-1$）。我们需要单点查链修改，于是可以用树上差分直接转化，变成子树查单点改，BIT 维护即可。

CF1483F Exam

给出字符串集合 $S$，求 $(i,j)$ 数量满足 $S_j\subseteq S_i$ 且不存在 $k$ 使得 $S_j\subseteq\ S_k\subseteq S_i$ 。

一个简单的想法是，对 $S$ 建好 ACAM 后，枚举每个 $S_i$ 作为最长串。尝试枚举 $S_j$，即从后向前枚举 $S_i$ 的所有前缀，假设 $S_i[1,r]$ 在 fail 树节点为 $u_r$，那么唯一合法的 $j$ 必然是 $u_r$ 向上跳的最近的终止节点 $p$，同时维护 $S_i$ 的最左侧子串匹配位 $l$，只要 $p$ 的左端点比 $l$ 小即合法。

看起来这个很对，但是没有考虑重复的情况。即若 $A\subset B\subset C$，其中 $C=A\cdots B\cdots$，那么在枚举到 $A$ 时，假设在 $AB$ 之间无合法匹配，那么 $l_A<l_B$，即 $A$ 会被算上一次贡献。

考虑如何修正，发现 $A$ 也是 $B$ 在 fail 树上的某个祖先节点。对 $B$ 到根进行 $+1$ 操作会导致 $A$ 权高于由自身产生的权值。即每个串出现次数与 fail 树上点权需相同。于是即可修正。

CF1801G/P13531

给出字符串集合 $S$ 与字符串 $t$。多次询问，每次询问给出 $(l,r)$，查询 $f(t[l,r])$。其中 $f(t[l,r])$ 表示满足 $[a,b]\subseteq[l,r]$ 的点对 $(a.b)$ 使得存在 $s_i\in S$，$s_i= t[a,b]$ 的点对数量。

考虑记录前缀答案，即设 $a_i=\sum\limits_{j=1}^i[ t[j,i]\in S]$，容易用 ACAM 建出的 fail 树上维护，答案应该是 $\sum\limits_{i=l}^r a_i$，但是会多算 $a<l\le b\le r$ 的情况。

设 $j$ 为最大的使得 $a_j$ 统计了上述非法情况的下标，那么所求即为 $f(t[l,j])+\sum\limits_{k=j+1}^r a_k$。这部分可以直接用线段树二分求出。

由于存在这样的 $a_j$，故 $t[l,j]$ 必然是某个 $s_k\in S$ 的后缀。考虑建出反串的 ACAM，问题就转化成对前缀 $s_{{rev_k}}[1,j-l+1]$ 查询所有 $s_{rev}\in S_{rev}$ 出现次数和。十分容易处理，设 $f_u$ 表示在 fail 树上 $u$ 到根终止节点个数，$g_u$ 表示在 trie 树上 $u$ 到根的 $f_v$ 之和，那么倍增找一下对应的前缀节点 $v$，$g_v+\sum\limits_{k=j+1}^r a_k$ 即所求。

P1393 Mivik 的标题

给出串 $S$，生成长度为 $n$ 字符集大小为 $m$ 的字符串 $T$，求 $T$ 包含 $S$ 的概率。

设 $f_i$ 表示 $T$ 首次出现 $S$ 在 $T[i-\vert S\vert+1,i]$ 不考虑后面填的方案数，容易发现答案就是 $\sum\limits_{i=\vert S\vert}^{\vert T\vert}f_im^{n-i}$。

考虑如何求 $f_i$，先钦定 $[i-\vert S\vert+1,i]$ 段为 $S$，总方案有 $m^{i-\vert S\vert}$，据此进行容斥，下面考虑非法情况。

• 若在 $[1,i-\vert S\vert]$ 中出现了 $S$，剩下的位置随便填。即 $\sum\limits_{j=\vert S\vert}^{i-\vert S\vert}m^{i-\vert S\vert-j}$。

• 若在加上 $S$ 的某个前缀 $p$ 后组成了完整的 $S$。这个 $p$ 显然是 $S$ 的一个 border，设这个长度为 $j$，从 $\sum\limits_{\vert\operatorname{border}\vert=j}f_{i-\vert S\vert+j}$ 转移。

border 的个数是 $\mathcal O(n)$ 的，复杂度就是 $\mathcal O(n^2)$ 的。考虑以 border 理论优化。

Border 理论告诉我们，字符串 $S$ 的 border 长度形成 $\mathcal O(\log n)$ 个等差数列，枚举这么多种等差数列，用前缀和优化即可。

P5287 [HNOI2019] JOJO

$Q$ 次操作，每次操作在当前串后加上 $x$ 个字符 $c$ 或者复原到第 $x$ 次操作。每次操作后，输出当前串每个前缀最长 border 长度之和。

复原操作是假的，完全可以建成操作树后在数上跑。

考虑添加操作，假设当前字符串为 $S$，操作为 x c。那么跳字符串的 Border，每次尝试向后拓展尽量多的 c，跳到 $0$ 或者向后拓展足够长的时候停止。但是由于这是压缩字符的做法，无法保证 KMP 的均摊复杂度，该做法最劣为 $\mathcal O(n^2)$。

考虑 border 与周期的关系。由于 border 形成 $\mathcal O(\log n)$ 个等差数列，而同属一个等差数列的 border 必然拥有相同的周期（这是 border 与周期的关系带来的）。因此我们只需看这类 border 的最大与次大即可，这样跳 border 的复杂度就降到 $\mathcal O(n\log n)$ 了。

另外，题目保证相邻添加的字符不同。考虑把新段视作二元组 $(x,c)$，那么相当于对这个做 KMP 匹配，然后随便几个条件即可。

还有，根据周期定理，若 $p$ 处形成公差 $t$ 的等差数列，直接跳到 $p\bmod t+t$ 即可。

似乎还可以直接维护对应位置，将连续一段独立开来，由于有 $\mathcal O(\log n)$ 可能的 border 进行匹配，因此建动态开点线段树，时空复杂度都是 2log。

P10716 【MX-X1-T4】「KDOI-05」简单的字符串问题

给出字符串 $S$，每次询问给出 $(i,k)$，求在 $S[1,i]$ 不重地出现至少 $k$ 次的 border $A$ 个数。

这个 $A$ 必然是 $S$ 的某个前缀，而长度为 $k$ 的前缀在 $S$ 的不重的出现次数至多是 $\left\lfloor \dfrac nk\right\rfloor$，一共有 $\sum\limits_{i=1}^n\left\lfloor \dfrac ni\right\rfloor\approx n\ln n$ 个状态。每次取越靠前的出现位置，答案一定不劣。因此考虑维护出每个前缀出现的位置。初始集合都是 $S_i={i}$，在失配树上启发式合并即可，复杂度 2log。

下面讨论如何求解答案。对于前缀 $S[1,i]$ 的最长 border，合法的 $A$ 只能在其于失配树到根的链上。另外，若一个 border 已经满足答案，那么其到根上的所有 border 也满足答案。于是考虑找到最深的满足出现次数 $\ge k$ 的 border，该 border 在失配树上的深度即所求，可以直接倍增加上二分实现。

P3181 [HAOI2016] 找相同字符

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

不妨每次枚举 $l_1,l_2$ 开头的两个极长子串，二者的 $\operatorname {lcp}(S[l_1,n_1],T[l_2,n_2])=t$ 就是最长的匹配，那么该 $(l_1,l_2)$ 对答案的贡献就是 $t$。那么所求即为 $\sum\limits_{l_1,l_2}\vert\operatorname{lcp}(S[l_1,n_1],T[l_2,n_2])\vert$。

那么问题就很简单了，把 $S$ 与 $T$ 拼起来：$S\texttt{#}T$，然后减掉对 $S$ 与 $T$ 单独求的和即可，这是一个经典问题。

P14591 [LNCPC 2025] Kanon

给出二进制串 $S$，对于每个 $k\in[1,n]$ 划分成 $k$ 个串，使得异或值最大。求最大异或值以及方案数，用题目给定方式输出结构。

首先，无论怎么异或，位数不变。因此若使异或最大，每次划分出的串长度尽量都为 $1$，剩下最长串。下面对 $k$ 的情况进行讨论。最大值的构造是容易的，下面讨论主要为

若 $S$ 前导零个数 $t\ge k-1$，这部分的贡献就是 $\dbinom{t}{k-1}$，即首个 $1$ 前面有 $t$ 个可选择的空隙，在这些空隙选 $k-1$ 分成 $k$ 组的方案数。特别的，当 $k=n$ 时，方案为 $1$。另外，若串全零，那么空隙应该为 $t-1$ 个。

下面讨论更一般的情况，此时已经固定位数为 $n-k+1$，只需后缀排序，容易找到对应 $k$ 的后缀，称其为代表元。而末位是与其他段异或的结果，因此只需与代表元后缀匹配上前 $n-k$ 位即可（注意模运算的存在，因此要对异或特殊处理），所有匹配的后缀都能作为答案。这个过程实际上就是按照 $height$ 数组来合并，即对 $height_i=k$ 在 $len=\min(k+1,len_{sa_i},len_{sa_{i-1}})$ 处合并 $(sa_i,sa_{i-1})$，可以用并查集实现。

P7361 「JZOI-1」拜神

给出串 $S$，每次询问给出 $[l,r]$，求 $S[l,r]$ 内出现次数至少为 $2$ 的最长子串长度（只需开头不同，可以重叠）。

注意到答案具有可二分性，

[ABC349G] Palindrome Construction

给出串 $S$ 每个位置作为中心的极长回文半径 $A_i$，试构造出字典序最小的 $S$ 或者报告不存在。

一种朴素的想法对于 $i$ 的回文半径 $A_i$，连接所有 $j\in[1,A_i],(i-j,i+j)$，然后贪心地进行染色。但是复杂度在平方级别。

考虑这是 Manacher 的逆过程，仿照 Manacher 的思路。假设当前记录的右端点为 $r$，取到最右的点为 $m$。那么对当前枚举的点 $i$ 进行分类讨论：

• 若 $m<i\le r$。找到 $i$ 关于 $m$ 的对称点 $2m-i$，$A_i\ge\min(A_{2m-i},r-i)$。你发现如果 $A_i$ 落在 $r$ 之内，那么这些边实际上在暴力拓 $m$ 时就已经处理过了，所以无需再加边。否则，同下种情况。

• 若 $i>r$。直接暴力拓展暴力加边。

以上实际上就是 Manacher 的过程，逆过来复杂度就能到线性了，并查集维护然后贪心染色即可。

计数

P6078 Sweets

所求即为 $\sum\limits_{i\in[a,b]}[x^i]\prod\limits_{j=1}^n\dfrac{1-x^{m_j+1}}{1-x}$。

拆开来，推式子：

对于 $\prod\limits_{i=1}^{n}(1-x^{m_i+1})$ 直接模拟乘法即可。对于模数的处理，注意到 $\dbinom{i+n-1}{i}=\dbinom{i+n-1}{n-1}$，$n$ 很小，然后算的时候先对模数乘上阶乘然后再除就好。

P3978 [TJOI2015] 概率论

设 $f_x$ 表示大小为 $x$ 的不同构二叉树个数，设 $g_x$ 表示大小为 $x$ 的不同构二叉树叶子总数。

$f_x$ 就是 Catalan 数，容易有 $f_x=\dfrac 1{x+1}\dbinom{2x}x$。

考虑怎么求 $g_x$，取一个点作为根，然后枚举左右子树大小，分别使当前计数对象作为左右子树，有 $g_x=2\sum\limits_{i=0}^{x-1}g_if_{x-1-i}$。

用生成函数写出来，$G(x)=\sum\limits_{i\ge1}2\sum\limits_{j=0}^{i-1}g_if_{i-j-1} \cdot x^i$。那么 $G(x)/x=2\sum\limits_{i\ge0}\sum\limits_{j=0}^ig_if_{i-j}\cdot x^i+1$。你发现就是 $F$ 与 $G$ 的卷积，即 $G(x)/x=2F(x)G(x)+1$，于是 $G(x)=\dfrac{x}{1-2x\cdot F(x)}$。

$F(x)$ 的收敛形式是 $F(x)=\dfrac{1-\sqrt{1-4x}}{2x}$，代入上式有 $G(x)=\dfrac{x}{\sqrt{1-4x}}$，展开即可。

CF1535F String Distance

首先发现 $f(S,T)$ 只有四个取值：$0,1,2,1337$。当 $S=T$ 时取 $0$，当去掉 $S,T$ 的 LCP 与 LCS 剩下的串 $s’,t’$，其一有序且二者字符可重集相同时为 $1$，当二者字符可重集相同时为 $2$，剩下情况为 $1337$。

于是有简单的 $\mathcal O(n^2\vert s_i\vert)$ 做法。考虑优化，只考虑等价类，容易求出每个串若干极长有序连续段，设为 $[l_i,r_i]$。分别建出正反链的 trie，把 $l_i-1$ 与 $r_i+1$ 代表的节点对打在二维平面上。然后能贡献到的必然前后缀都在 $l_i-1$ 与 $r_i+1$ 的子树内，二维数点即可。

CF1051E Vasya and Big Integers

给出大整数 $N,l,r$，将 $N$ 划分成多段数，使得每段数不含前导零，且在 $[l,r]$ 之间。求方案数。

位数均不超过 $10^6$。

下面 $N_{i,j}$ 表示 $N$ 的第 $i$ 位到第 $j$ 位组成的数。

容易设计 $\mathcal O(n^2)$ 的 DP，$f_i$ 表示最后一次划分以 $i$ 结尾的方案数，有 $f_i=\sum\limits_{j=1}^{i-1}[N_{j+1,i}\in[l,r]]f_j$，注意到这个东西可以前缀和优化，找到最大 $p$ 的满足 $N_{p+1,i}\ge l$，以及最大的 $q$ 满足 $N_{q,i}>r$，那么这里的答案就是 $\sum\limits_{j=q}^pf_j$。

这里的 $p,q$ 可以直接从 $l,r$ 的位数来找，在判断大小关系时考虑求出二者 LCP 后比较下一位，用 Z 函数也好 Hash 也好总之非常好写。

CF1511F Chainword

给出 $n$ 个单词。假设这些单词能组成长度为 $m$ 的字符串集合 ${S}$，设有 $k_s$ 种方案组成 $s$，求 $\sum\limits_{s\in S}k_s^2$。

$n\le 8,m\le10^9$。

原题面给出的形式是可重的两两匹配，如果直接 dp 平方是难做的，考虑就用题面给出的提示来做。

建出字符串集合的 trie 树，设 $f_{i,j,k}$ 表示已经已经算了长度为 $i$，第一个走到节点 $j$，第二个走到节点 $k$ 的方案数。讨论一下如果当前是终止节点要不要继续走。于是有简单的 $\mathcal O(m\cdot(n\vert s_i\vert)^2)$ 的做法。

考虑把节点对的转移矩阵写下来，矩阵优化一下就做完了。具体的，用 BFS 把所有节点状态都跑出来，然后将二元 $(i,j)$ 映射到单点。设 $M_{i,j}$ 表示从状态 $i$ 到状态 $j$ 的方案数，答案就是 $M^m$ 中，由根根对到所有终止节点对的方案和。

CF1437G Death DBMS

ACAM 模板题，不写了。

CF1073G Yet Another LCP Problem

给定一个长度为 $ n $ 的字符串 $ s $ 和 $ q $ 个询问。每个询问包含两个整数集合 $ a_1, a_2, \dots, a_k $ 和 $ b_1, b_2, \dots, b_l $。对于每个询问，计算 $ \sum\limits_{i = 1}^{k} \sum\limits_{j = 1}^{l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])} $。

先对对字符串进行后缀排序，然后按照排名给 $a_i$ 以及 $b_i$ 分别排序。然后从左到右枚举 $a_i$，左边的 $b_i$ 与其 LCP 不增，线段树二分出首个比新 height 小的 LCP，然后对这些赋值再求和，右边也是类似处理，就能做到线性对数的复杂度了，不用线段树用单调栈也可以，复杂度更优，但是瓶颈还是对 $a_i,b_i$ 的排序。

懒得写了。

P4762 [CERC2014] Virus synthesis

对 $s$ 建出 PAM 后，设 $f_i$ 表示搞出来 $i$ 节点的最小操作次数，答案就是 $\min\limits_{i} (f_i+n-len_i)$。咋转移呢，初始显然可以是 $len_i$。一个显然的观察是操作 2 越多越好，结合回文串的优秀性质，首先从其父节点而来，表示在操作 2 前加了一个字符，即 $f_i\gets f_j+1$。也可以从 $fail_i=k$ 上来，即 $f_{i}\gets len_i/2-len_k+f_{k}+1$，注意这个 $len_k\le len_i/2$。

用 BFS 转移即可。

动态规划

CF809D Hitchhiking in the Baltic States

容易仿照一般 LIS 问题设：$f_i$ 表示长度为 $i$ 的 LIS 结尾的最小时间。外层枚举城市，内层进行转移，$\mathcal O(n^2)$。

考虑进一步优化，把转移式写下来：