LOJ3685 难度 2

考虑寻找合法解的性质，发现如果有解，那么一定存在一种方案使得每个人开始走之后，直接不停顿地走到终点。

证明：考虑合法解中某个人 $i$ 的相邻两次行动 $A\to B,B\to C$，由于走的是最短路径，必有 $A\neq B\neq C$。

我们考虑如果这两次行动在总的行动序列上不相邻，它们中间有若干次行动，由于此时 $i$ 位于点 $B$，因此其他人的任意行动都不能经过 $B$。以 $B$ 为根建树，那么中间的行动可以划分为三部分：

• 完全在 $A$ 子树内的部分
• 完全在 $C$ 子树内的部分
• 其他的部分

借用官方题解的图：

于是我们可以重排操作序列为：

• 先进行完全在 $C$ 子树内的部分。
• 然后让 $i$ 这个人从 $A\to B\to C$。
• 然后进行 $A$ 子树内的部分和其他部分。

这样一直操作下去，一定可以构造出一种解满足每个人开始走之后，直接不停顿地走到终点。

于是我们考虑两个人 $(i,j)$ 如果满足 $S_i\in\text{path}(S_j,T_j)$ 或者 $T_j\in \text{path}(S_i,T_i)$，那么 $i$ 就得在 $j$ 前面走。这样会连出来一张有向图，如果是 DAG 就有解，否则无解。

直接连会得到 $O(M^2)$ 条边，许多数据结构都能将其边数优化至 $O(M\log N)$。优化之后就可以过了。

LOJ3692 难度 2

对于修改，如果修改了和 $u$ 距离不超过 $D$ 的一个点 $v$，我们发现在 $\text{LCA}(u,v)$ 处计算贡献似乎不可避免地要带上 log。设 $\text{dist}(u,v)=x\le D$，我们考虑在 $\text{LCA}$ 的 $\lfloor\frac{D-x}{2}\rfloor$ 级祖先 $p$ 的位置计算贡献。

那么要求 $\text{dist}(u,p)+\text{dist}(p,v)=D$ 或者 $D-1$。可以发现，这样的确能不重不漏地统计完所有贡献。具体来说，对每个点 $u$ 我们记录 $f_{u,i}$ 表示 $u$ 子树内和他距离为 $i$ 的所有点进行的修改。修改时我们枚举 $u$ 的祖先 $p$，将 $f_{p,D-\text{dist}(u,p)}$ 和 $f_{p,D-1-\text{dist}(u,p)}$ 计入这次贡献。查询时枚举 $v$ 的祖先 $p$，把 $f_{p,\text{dist}(u,p)}$ 累计进答案。

有一个细节是 $\text{LCA}$ 可能不存在 $\lfloor\frac{D-x}{2}\rfloor$ 级祖先，我们在根节点往上再加 $D$ 个点即可。

总复杂度 $O((N+Q)D)$。

QOJ7088 难度 3

考虑一个串 $a$，考虑找到所有的 $i,k$ 使得 $a[i,i+k-1]=a[i+k, i+2k-1]$。

枚举 $k$，设 $b_i=[a_i==a_{i+k}]$，那么我们只需要找到 $b$ 中所有长度 $\ge k$ 的连续段。

注意到连续段的段数不超过 $\lfloor n/k\rfloor$，考虑一段一段找。发现长度 $\ge k$ 就至少需要经过 $k,2k,\cdots$ 这些位置中的一个，考虑枚举 $x=ik$，算出经过 $x$ 的极长连续段长度。那么只需要查询 $[1,x],[1,x+k]$ 的最长公共后缀与 $[x,n],[x+k,n]$ 的最长公共前缀即可。SA 配合 ST 表容易做到 $O(n\log n)$。

现在我们找到了一个极长的连续段 $[L,R]$，那么相当于要对每个 $i=L,L+1,\cdots,R-k+1$，连边 $(i,i+k)$，边权为 $w_k$。我们按照 $w_k$ 从小到大考虑，那么只需要能找到那些真的发生合并的位置就好了，因为虽然边数超过了平方级别，但是合并次数至多是 $n-1$。

具体地，我们考虑建一个 ST 表，这个 ST 表的含义是：如果 $F[x][i] == F[y][i]$，说明我们可以确定 $x,x+1,...,x+2^i-1$ 分别和 $y,y+1,...,y+2^i-1$ 有连边；如果不等，那么我们不确定他们是不是真的连好了（也就是说，可能这两个数不相等，但是他们代表的区间的确有对应连边）

现在考虑如果我们要对 $[i,i+k-1]$ 和 $[j,j+k-1]$ 连边，首先拆成两个长度为 $2^p$ 的区间连边，那么要找到这个区间中所有的实际有效（造成连通块合并）的连边，就只需要从 $F[i][p]$ 和 $F[j][p]$ 往下递归，做一个类似在线段树上递归的过程；然后我们在第 $p$ 层把 $F[i][p]$ 和 $F[j][p]$ 对应的极大连通块合并，可以启发式合并或者直接并查集维护。

这样每一层都只会有最多 $n$ 次合并，总的合并次数就是 $O(n\log n)$；如果在并查集中实现路径压缩+按秩合并，复杂度就是 $O(n\alpha(n)\log n)$。注意虽然有 $n\log n$ 次区间连边，但总共的有效合并次数还是 $n\log n$ 级别，所以复杂度只有 1 个 $\log n$。

Luogu10365 难度 3

定义区间 $[l_i,r_i]$ 能到 $[l_j,r_j]$ 当且仅当只往 $[l_i,r_i]$ 开始倒水，最后 $[l_j,r_j]$ 会被覆盖。

只需要求能到达每个区间的区间个数。设 $cnt_i$ 为能到 $i$ 的区间个数，则答案为 $\sum \frac{1}{cnt_i}$。

对每个区间 $[l_i,r_i]$，找到 $l$ 上面的第一个区间和 $r$ 上面的第一个区间，设这两个区间分别为 $p_i,q_i$，我们建两棵树，第一棵树上 $i$ 的父亲为 $p_i$，第二棵树上 $i$ 的父亲为 $q_i$。

那么我们会从 $[l,r]$ 一路向上扩展，直到被完全覆盖。找到这个完全覆盖的，那么合法区间就是覆盖过程中经过的若干段阴影区域拼起来。这些阴影部分可以被差分为 $r$ 往上跳的若干个矩形减去 $l$ 往上跳的若干个矩形内的线段个数。于是只需要倍增求一下链上和就好了。

这里还需要求第一个被覆盖到的区间，发现这就是支配树上它的父亲，只需要求 DAG 的支配树。这个很好求：任取拓扑序，对每个 $u$，其入边分别为 $v_1,v_2,\cdots,v_k$，找到 $\text{LCA}(v_1,v_2,\cdots,v_k)$，则 $u$ 的支配点就是这个 LCA。连边接着递推即可。

ARC105F 难度 3

设 $f(S),g(S)$ 分别表示从点集 $S$ 内选边，得到一个连通/任意二分图的方案数，其集合幂级数为 $F,G$。自然地，有 $G=e^{F}$。

考虑怎么算 $g$，发现有一个自然的想法是，钦定每个点的颜色，然后异色边任选，同色边一定不能选。但这样会有问题，对于一个有 $x$ 个连通块的二分图，我们会将其计算 $2^x$ 次。

记这样算出来的值是 $h(S)$，其集合幂级数为 $H$。那么实际上，我们发现有 $H=e^{2F}$，因为每多一个连通块，方案数就会再乘 $2$。由于 $G=e^F$，得到 $G^2=H$。于是 $F=\ln G=\ln \sqrt{H}=\frac{1}{2}\ln H$。

$H$ 可以用一遍子集卷积算出，综上所述，总复杂度 $O(N^22^N)$。

QOJ8049 难度 3

考虑给每个合法序列 pair $(x_{1\cdots p},y_{1\cdots q})$ 对应唯一的一个加数的顺序，每次如果当前 $\sum x<\sum y$ 就加一个 $x$，否则加一个 $y$。那么每种方案对应唯一的顺序，且每个顺序中，$\sum x-\sum y$ 的值永远在 $[-V,V]$ 之间。

于是 $dp_{i,j,k}$ 表示加入了 $x_{1\cdots i},y_{1\cdots j}$，目前 $\sum x-\sum y=k$ 的方案数即可。

每次如果 $k<0$ 就转移到 $(i+1,j,\cdot)$，否则转移到 $(i,j+1,\cdot)$。转移用前缀和优化，复杂度 $O(n^2V)$。

LOJ3688 难度 3

显然任意时刻 $X,Y$ 肯定是最终串的一个区间，因此我们考虑区间 DP。

设 $f(l,r)$ 表示合成 $[l,r]$ 所需的最小代价，分最后一次有效操作是粘贴还是加字符讨论。

如果是加字符，有 $f(l,r)\leftarrow f(l,r-1)+A$。

如果是粘贴，那么如果粘贴了一个 $[k+1,r]$，考虑到剪切的时候会直接变成空串，于是我们一定是先用最小代价构造出 $s[k+1,r]$，然后需要算出，如果剪贴板里面是 $s[k+1,r]$，那么构造出 $s[l,r]$ 最少需要多少代价。

如果粘贴一次还不如直接加字符，即 $A\times (r-k)<C$，那显然没有用。

否则我们应该粘贴尽可能多次，也就是说要在 $[l,r]$ 中找到尽可能多的不交子串 $s[k+1,r]$。

考虑先枚举 $r$，然后枚举 $k$，对所有的 $l$ 做贡献。枚举完 $r,k$ 之后，设 $c_i$（$i\le r$）为 $[i,r]$ 中子串 $[k+1,r]$ 的最多不交出现次数，我们相当于要做转移

注意到 $c_i\le \frac{r}{r-k}$，考虑对一段相同的 $c_l$ 一起做贡献，那么是一个区间对公差为 $A$ 的等差数列 chkmin 的形式，可以简单维护。这样对一个 $r$，只需要 $O(r\log r)$ 次区间 chkmin。进一步发现区间可以放宽成前缀，于是可以 $O(1)$ 进行一次操作。

现在还需要求一个 $p$ 前面 $[l,r]$ 最后一次出现的位置，注意我们会对一个 $[l,r]$ 询问若干递减的 $p$，在 SAM 上定位到 $[l,r]$ 这个节点，然后在 endpos 集合里维护一个指针即可做到均摊 $O(1)$。当然也许用 hashmap 也可以做到 $O(1)$。

综上，总复杂度 $O(N^2\log N)$。

LOJ3490 难度 4

首先，我们有 $O(q(n^2+m))$ 的算法，即每次跑一遍 dijkstra，同时记录到每个点的最短路以及这个最短路对应的时刻。可以证明只要这样就能得到最优解。

把路径分成两类：在一天内完成的，和至少有一次等待到下一天的。

对于在一天内完成的路径，我们考虑找到其中限制最严（也就是经过这条边的时间最接近他的限制时间）的一条边 $(u,v,L,C)$，假设我们是从 $s$ 走到 $t$，起始时间为 $A$，如果走到点 $u$ 的时候时刻为 $B\le C-L$，那么我们知道这条边的 $C-L-B$ 是所有边里面最小的一个。

我们把起始时刻加上 $C-L-B$，可以发现路径仍然合法。于是有如下的算法：枚举每条边 $(u,v,L,C)$，计算 $dis_x$ 表示想要从 $x$ 走到 $u$，满足：

• 整个过程必须在一天内完成。
• 到达 $u$ 时，当前时刻 $\le C-L$。

这种情况下所需的最小时间。这可以通过一遍 dijkstra 在 $O(n^2+m)$ 的时间内算出，同时也可以算出 $tim_x$ 表示如果要求能走这个最短路，$x$ 的起始时间最晚是多少。再通过一遍 dijkstra 算出 $to_y$ 表示从 $v$ 到 $y$，起始时间为 $C$，所需的最少时间（这个过程同样必须在一天内完成）。

算出这些之后，我们就可以计算 $(u,v,L,C)$ 这条边对所有点对 $(x,y)$ 的贡献，即对于起始时间 $A\le tim_x$，都有一种 $dis_x+to_y+L$ 的方案。

现在考虑跨越多天的路径，注意到如果在某个城市 $u$ 进行等待，一定是等待到第二天的 $0$ 时刻，然后在 $L$ 时刻出现在某条边 $(u,v,L,C)$ 的终点 $v$。

于是类似地，我们枚举路径上第一条进行等待的边 $(u,v,L,C)$，同理算出 $tim,dis,to$（只不过此时从 $v$ 开始走的时候，我们允许它跨越多天完成），更新答案即可。

最后再对每个点对 $x,y$，我们把贡献到 $(x,y)$ 上面的若干条路径按照 $tim$ 排序，然后预处理后缀 min，即可在 $O(\log n)$ 的时间内回答一组询问。这里可能要对 $O(n^2)$ 个长度为 $O(m)$ 的数组排序，但注意到对于一个 $x$，所有 $y$ 的分段点总共只有 $O(m)$ 个，于是只需要进行 $n$ 次排序。

综上，总复杂度 $O((n^2+m)m+nm\log m+q\log n)$。

Luogu10356 难度 4

考虑两个单调的序列，长度分别是 $x,y$，他们合并起来的最小的 $f$ 怎么算。

发现合并之后会得到一个长度为 $x+y$ 的序列，同时会分成 $y+1$ 段，而且显然新插入的数要么可以放到左边的段内，要么可以放到右边的段内，于是下界是 $\lceil(x+y)/(y+1)\rceil$。

我们发现下界一定是可以取到的。钦定 $x$ 的划分，以及划分点分到左边还是右边，直接顺次填入，如果出现了 $x_i<y_j<x_{i+1}$ 这样导致两个段合并的，发现总可以把 $j$ 向前提一位或者向后放一位从而分隔开。那么这样交换会不会相交呢，发现需要这一段长度为 $1$，而且两边都向另一侧钦定，发现这个时候一定不如直接向 $len=1$ 的这一侧钦定。于是答案就是 $\lceil(x+y)/(y+1)\rceil$。

接下来考虑一般情况，把 $A,B$ 分段，如果答案想要为 $x$，那么需要两边分的段数都够用。设左边的段长构成序列 $a$，右边是 $b$，考虑 $\lceil(a_i+y)/(y+1)\rceil\le x$，即 $(a_i+y)/(y+1)\le x$，可以算出

于是只需要 $\sum \lfloor (a_i-2)/(x-1)\rfloor \le |B|$。另一边也一样。

注意到两边只有一个会卡满约束。考虑对一个 $x$ 算有多少区间符合条件，用总数减掉两边分别卡掉的即可。考虑怎么算卡掉的，发现相当于取若干整段和两个散段。

枚举左端点 $l$ 所在整段，对于 $l,r$ 同段的形式，此时算出的 $\lfloor (r-l+1)/(x-1)\rfloor\le \lfloor n/(x-1)\rfloor$， 枚举结果容易算出方案数，进而计算贡献；对于 $l,r$ 不同段的，我们可以从分段点处分开，那么贡献为 $l$ 处的散段贡献与 $r$ 左边的若干整段和一个散段贡献之和，也就是要算

其中 $w_l$ 表示 $l$ 到这一段右端点的贡献，$v_r$ 表示 $r$ 左边的若干整段和一个散段的贡献之和，$g(k)$ 表示 $B$ 中选一个长度 $\le k$ 的区间的方案数，这个是一个前面二次函数后面平着的形式。

这个形式不完全是二次函数，直接维护一次项和二次项可能会算错后面的部分（也是我场上 FST 的原因）。

注意到 $w_l$ 不超过这一段的段长除以 $x-1$，我们考虑枚举 $w_l$ 的值，算出 $\sum_r g(w_l+v_r)$，这样复杂度也就是调和级数。双指针维护最大的 $p$ 满足第一个 $w_l+v_r\ge m$ 的 $r$ 在这一段内，然后可以算出具体的分段点在哪里。

那么对 $p$ 前面段内的 $r$ 我们需要维护 $\sum v_r,v_r^2$，后面段内的 $r$ 直接维护个数即可，这一段的一个前缀的 $\sum v_r,v_r^2$ 有一个等差数列求和以及等差数列平方和的形式，可以 $O(1)$ 算出。

综上，总复杂度 $O(n\ln n)$。

• 这个实现起来非常的麻烦，建议你先写一个最简单的暴力，然后一点一点地优化。

QOJ8543 难度 4

考虑如果确定了每个字符串的长度以及 $S_1$，那么实际上字符串的形态是确定的：如果 $len_i>len_{i+1}$，那么一定是保留一段前缀；否则一定是不断循环，直到长度为 $len_{i+1}$。

考虑一个 $S_i$，发现不管怎样一定是加一段前缀，或者删一段后缀，这样得到的所有 $S_i$ 都是由 $S_1$ 的若干个前缀拼接得到。考虑如果拼的前缀长度分别为 $a_1,a_2,\cdots,a_k$，那么如果某两个 $S_i,S_j$ 的 $a$ 序列相同，显然 $S_i=S_j$；否则我们令 $S_1=\texttt{abbbb}\cdots$，那么只要两个 $S_i,S_j$ 的 $a$ 不同，就一定有 $S_i\neq S_j$。

考虑怎么样的 $a$ 序列可以被生成出来，一开始 $a=(n)$，每次可以加上若干个 $a_1,a_2,\cdots,a_i,[x\le a_{i+1}]$，或者删掉末尾的若干个元素，然后把最后一个元素减小。我们考虑想生成一个目标 $a$ 序列的话，发现只要 $a_i\le a_1$，我们就可以直接加一个 $a_i$ 到末尾去；否则我们一定得不到 $a_i$。所以 $a$ 序列合法当且仅当 $\forall i,1\le a_i\le a_1$。

于是要算 $F(n)$，就只需要计数满足 $\sum a_i\le n,1\le a_i\le a_1$ 的序列 $a$ 个数。

枚举 $a_1=k$，相当于计数 $\sum a_i\le n-k,1\le a_i\le k$ 的序列个数；枚举个数 $m$，容斥钦定 $j$ 个 $a_i>k$，可以得到总的方案数是

此时可以得到 $O(N^2\log N)$ 的解法：对每个 $n=1,2,\cdots,N$ 暴力计算即可。通过对这个式子强行找递推式可以得到更优的做法，但更简单~~（并不简单）~~的方法是使用 GF：考虑答案的 GF

根号分治，取 $B=\lfloor \sqrt{N}\rfloor$。考虑 $k<B$ 的时候，暴力展开 $\frac{x^k}{1-2x+x^{k+1}}$，可以得到一个 $O(N)$ 的递推式：$f_i-2f_{i-1}+f_{i-k-1}=[i=k]$，于是可以 $O(N)$ 计算出他对所有 $F$ 的贡献，这部分复杂度 $O(N\times B)$。

对于 $k\ge B$，我们重新写一下上面的式子：

这里第二个等号利用了 $\frac{1}{1+t}=\sum_{i\ge 0}(-1)^it^i$。

注意我们只需要计算 $j+B(j+1)\le N$ 的 $j$ 的贡献，于是这样的 $j$ 只有 $O(\frac{N}{B})$ 个。考虑我们设

那么 $ans(x)=\sum_{j=0}^{n/B}\frac{G_j(x)}{(1-2x)^{j+1}}$。我们一开始令 $ans(x)\leftarrow 0$，然后每次 $ans(x)\leftarrow \frac{ans(x)+G_j(x)}{1-2x}$ 即可。

算一项 $G_j$ 是 $O(\frac{N}{j})$ 的，但做一次除法都是 $O(N)$ 的，于是这部分复杂度 $O(\frac{N^2}{B})$，总复杂度 $O(N\sqrt{N})$。

Luogu11949 难度 5

下文不区分 $n,m$。

• Subtask 3 的做法

最后相当于选取 $a,b$ 中各一个区间，最大化它们的 $\min$ 乘上 $\text{len}$ 之和。不难发现，我们选取的区间一定满足往左右扩展会导致 min 减小，或者干脆就无法扩展也就是顶到边界。那么 $a$ 中选取的区间肯定是笛卡尔树上的区间；$b$ 中选取的区间则要么是完整的笛卡尔树区间，要么是某个原序列笛卡尔树区间和询问区间 $[l,r]$ 的交。

在 subtask 3 中，询问区间总是笛卡尔树区间，于是只需要考虑选取一个完整笛卡尔树区间的情况。我们可以先 $O(n\log n)$ 提前对 $O(n)$ 个笛卡尔树区间预处理答案，然后做一个二维数点。总复杂度 $O((n+q)\log n)$。

• $O((n+q)\sqrt{n})$ 做法

根据上面的分析，我们发现可以在 $O((n+q)\log n)$ 时间内解决选取完整笛卡尔树区间的 case，现在就剩下选取不完整区间的情况。这意味着一定是选询问区间的一段前缀或者一段后缀。我们不妨就假设选取的是一段后缀。

设 $A_i$ 表示序列 $a$ 中满足所有数都 $\ge i$ 的区间的最长长度，我们考虑扫描线扫 $r$，维护序列 $B$，其中 $B_i$ 表示以当前 $r$ 为右端点的区间中，$\min\ge i$ 的区间的最长长度；那么如果没有 $l$ 那边的限制，答案就是 $i\times(A_i+B_i)$ 的全局最大值；进一步我们发现 $l$ 那边的限制其实可以这样处理：我们钦定的 $B$ 这一侧的最小值必须得严格大于整个询问区间 $[l,r]$ 的最小值，对于选取整个区间的情况单独考虑。这样可以发现区间就不会超出 $l$ 了。

现在考虑如何维护 $B$，发现 $r\to r+1$ 的时候相当于把 $[1,b_{r+1}]$ 做区间 $+1$，以及 $[b_{r+1},\infty)$ 覆盖为 $0$；以及还需要查询一个后缀中 $i\times (A_i+B_i)$ 的最大值，其中 $A_i$ 是提前预处理的定值。这个问题可以使用分块配合凸包维护，做到 $O((n+q)\sqrt{n})$。实测是能过的。

• $O(n\log^3 n+q\log^2n)$ 做法

我们考虑假如询问区间是 $[ql,qr]$，选取了笛卡尔树区间 $[l_i,r_i]$，笛卡尔树区间中的最小值为 $m_i$，那么此时实际的区间是 $[ql,qr]\cap [l_i,r_i]$。不妨考虑 $ql\le l_i\le qr\le r_i$ 的情况，其贡献为

其中 $A_y$ 表示序列 $a$ 中最长的一个区间，满足区间中的数全部 $\ge y$。

这是一个关于 $qr$ 的函数，我们可以提前按照 $m_i$ 递增扫描线，维护一个可持久化李超树就可以支持 $O(\log n)$ 单次查询出一个 $f_i(x)$ 的值。现在我们要查询所有满足 $ql\le l_i\le qr\le r_i$ 的 $i$，他们的 $f_i(qr)$ 的最大值。

注意到一个性质：任意两个 $i,j$，他们的 $f_i(x),f_j(x)$ 两个函数至多只有一个交点。因此我们可以使用李超树来维护 $f_i(x)$ 的单点处最大值；对于 $ql\le l_i\le qr\le r_i$ 的限制，扫描线扫 $ql$，每次遇到一个 $[l_i,r_i]$ 的时候做一个李超树区间插入，查询只需要在 $O(\log n)$ 个节点上求一次值。

最后把另一种情况反过来再做一遍，复杂度就是 $O(n\log^3n+q\log^2n)$。