QOJ8593 难度 2

首先，我们在最终的图中找到一个拓扑序，然后对这个排列做一下置换。下面我们钦定每次给出的 $x,y$ 都满足 $x<y$；一个数 $x$ 当前能被确定，当且仅当它能到达 $x-1$ 个点，且有 $n-x$ 个点能到达它。

我们考虑 $x-1$，发现他必须得能从 $x$ 直接到达；进一步考虑 $x-2$，发现它的入边里面至少得有 $x-1$ 或 $x$。

依此类推，我们可以发现，如果设 $a_i$ 表示 $i$ 的入边中编号最小的点，那么 $x$ 能到达 $1,2,\cdots,x-1$，当且仅当对所有的 $i=1,2,\cdots,x-1$，都有 $a_i\le x$。同理设 $b_i$ 表示 $i$ 的出边中编号最大的点，那么还需要对所有的 $i>x$，都有 $b_i\ge x$。

每次修改对 $a,b$ 的影响是 $O(1)$ 的，简单用线段树维护下就行。时间复杂度 $O((n+m)\log n)$。

LOJ3687 难度 2

首先，当 $i<j$ 时，$T_i\le T_j$ 等价于 $s[i+1,j]\le s[i,j-1]$。

也就是说，区间 $[i,j-1]$ 内第一个满足 $s_k\neq s_{k+1}$ 的位置 $k$ 需要满足 $s_k\ge s_{k+1}$。

另一方面，如果 $i>j$，那么相当于区间 $[j,i-1]$ 内第一个满足 $s_k\neq s_{k+1}$ 的位置 $k$ 满足 $s_k\le s_{k+1}$。

称 $i<j$ 的限制 $T_i\le T_j$ 为第一类约束区间 $[i,j-1]$，否则为第二类约束区间 $[j,i-1]$。

直接记录 $f(i,j)$ 表示前 $i$ 个字符，$s_i=j$ 的方案数。转移时，我们分三种情况讨论：

• $s_i=s_{i+1}$：此时没有约束，直接转移 $f(i,j)\to f(i+1,j)$。
• $s_i>s_{i+1}$：枚举上一个 $s_k\neq s_{k+1}$ 的位置 $k$，那么要求 $i$ 能满足所有 $l>k,r\ge i$ 的 $[l,r]$ 的约束，也就是不能存在第二类约束区间，满足 $k<l\le i,r\ge i$。合法的 $k$ 是一段后缀，可以拿 set 简单维护得到这段后缀。得到合法后缀之后有 $f(k+1,j)-f(k,j)\to f(i+1,[x<j])$，可以简单做到 $O(1)$ 转移。
• $s_i<s_{i+1}$：类似。

综上，总复杂度 $O(n|\Sigma|+n\log n)$，其中 $|\Sigma|=26$。

ARC148E 难度 3

考虑把数分成 $\ge\frac{K}{2}$ 和 $<\frac{K}{2}$ 的，那么 $<\frac{K}{2}$ 的一定不能相邻，$\ge\frac{K}{2}$ 的一定可以相邻，而如果分别再两边，那么 $x,y$（$x<\frac{K}{2}\le y$） 可以相邻当且仅当 $x+y\ge K\iff \frac{K}{2}-x\le y-\frac{K}{2}$。

于是我们按照 $|x-\frac{K}{2}|$ 从大到小的顺序插入每种数（如果有 $x+y=K$ 那么我们先插入大的）然后把方案数乘起来即可。具体来说我们分类讨论一下插入的这个数 $x$ 是 $\ge \frac{K}{2}$ 还是 $<\frac{K}{2}$，设其个数为 $y$，维护满足当前两边都是 $\ge \frac{K}{2}$ 的数这样的空隙个数 $s$，那么

• 如果 $x\ge \frac{K}{2}$，那么 $x$ 只能和 $\ge\frac{K}{2}$ 的数相邻。不难发现不管怎么插入，空隙的个数一定只会增加 $y$。于是方案数是 $\binom{s+y-1}{y}$，然后我们令 $s\leftarrow s+y$。
• 如果 $x<\frac{K}{2}$，那么 $x$ 可以放在任意一个空隙里面，不难得到方案数为 $\binom{s}{y}$，然后插入一个肯定会减少一个空隙，所以需要把 $s\leftarrow s-y$。

总复杂度 $O(n\log n)$，瓶颈在排序。

LOJ2472 难度 3

考虑依次给 $i=1,2,\cdots,n$ 填上数，每次尽量填最大的。考虑什么时候 $i$ 填上 $x$ 是合法的。考虑 Hall 定理，发现左部点约束最严的时候肯定是找一个已经填过的点 $u$，然后对所有 $d_v\ge d_u$ 的 $v$，选出 $v$ 的子树内的所有点，也就是说我们会选一个后缀的子树的并。形式化地，对每个已经填过的点 $u$，所有 $d_v\ge d_u$ 的 $v$ 的子树内未填的点并起来的大小不能超过 $\ge d_u$ 且尚未被填入的格子个数。

维护 $w_i$ 表示如果在判定中选择分界点为 $i$，$\ge i$ 的剩余空位数减去所有 $d_u\ge i$ 的子树并中未填点数的差，那么当前状态合法当且仅当 $w_i\ge 0$ 对所有 $i$ 成立。

考虑给 $u$ 填入 $x$ 有什么影响，发现对前一项的影响是所有 $i\le x$ 的 $w_i\leftarrow w_i-1$。考虑后一项会发生什么变化，我们发现由于树的 BFS 序就是 $1,2,\cdots,n$，因此 $u$ 的子树内一定完全是空的，祖先一定是满的。因此，设 $v$ 是 $u$ 的父亲，显然只有 $i\le x$ 的 $w_i$ 会发生改变，具体地：

• 当 $i \le d_v$ 时这个子树并中未填的点的个数会 $-1$，导致实际的 $w_i$ 不改变；
• 当 $d_v<i\le x$ 时，子树并会多出 $\text{size}_u-1$，导致实际的 $w_i$ 的变化为 $w_i\leftarrow w_i-\text{size}_u$。

因此，实际的影响就是：对所有 $d_v<i\le d_u$，令 $w_i\leftarrow w_i-\text{size}_u$。那么要想维持 $w_i\ge 0$，就只需要找到 $d_v$ 后面的最大的 $x$，使得对 $i\in (d_v,x]$，均有 $w_i\ge \text{size}_u$，然后将这个区间都减去 $\text{size}_u$。线段树维护即可，时间复杂度 $O(n\log n)$。

LOJ6669 难度 3

首先指出本题我们需要的两个工具：

• 询问每个点 $u$ 到 $1$ 的距离就可以知道每个点的深度 $\text{dep}_u$。
• 接下来，如果我们已经确定了 $u$ 的每一级祖先，询问 $d(u,v)$ 即可得到 $\text{LCA}(u,v)=z$ 的深度（具体地，$\text{dep}_z$ 满足 $\text{dep}_u+\text{dep}_v-2\times \text{dep}_z=d(u,v)$），进而得到 $\text{LCA}(u,v)$。

考虑按照 BFS 序，即深度从小到大的顺序构建整棵树，并维护这棵树实时的轻重链剖分结果。

加入一个新一层的点 $u$ 时，我们先找到 $1$ 所在重链的链底 $x$，找到 $\text{LCA}(u,x)=y$。如果 $y=x$，说明 $u$ 的父亲就是 $x$，我们就确定了 $u$ 的父亲；否则，$u$ 一定在 $y$ 的另一个子树内（注意树是二叉树，因此一定可以确定到底是哪个子树）。这样只会跳 $O(\log n)$ 次轻边，可以在 $O(n\log n)$ 次询问内确定所有点的父亲。

询问复杂度 $O(n\log n)$，时间复杂度 $O(n^2)$。

QOJ4549 难度 3

$f(u)$ 表示 $u$ 子树的 SG 值，那么转移相当于选一个 $v$，删掉这条链后必然会形成若干子树，该后继的 SG 值就是这些子树的 SG 值的 xor 和。最后还需要对这些东西取 mex。

考虑所有这些后继状态，发现如果我们设 $S(u)$ 表示 $u$ 子树的所有后继状态的 SG 值构成的集合，实际上对于一个点 $u$，设其儿子分别为 $v_1,\cdots,v_k$，那么他的 $S(u)$ 就是：将每个 $S(v_i)$ 异或上所有 $j\neq i$ 的 $f(v_j)$，然后再取并集，再插入所有 $f(v_i)$ 的异或（表示第一次操作删除了 $u$ 自己）。

那么我们就是要用数据结构维护一个集合，支持全局异或，插入，合并，查询全局 mex 这三种操作。

使用 01trie 维护即可，单组数据复杂度 $O(n\log n)$。

Luogu5287 难度 4

我们来刻画本题这样的字符串的 border：可以发现，一些后缀段能和一些前缀段构成 border，需要他们除了开头和结尾之外的二元组 $(x,c)$ 都完全相同。对于首尾两个二元组，需要后缀的开头段比前缀长，前缀的结尾段比后缀长。

考虑直接把二元组 $(x,c)$ 当作字符来进行字符串匹配。我们考虑加入一个 $(x,c)$ 对答案的贡献。如果没有撤销操作，我们可以直接暴力跳 fail link 并记录当前遇到的所有节点中 $c$ 这条出边长度的前缀最大值 $w_1$，每遇到一个更大的 $w_2$，设这里前面的总长度为 $L$，我们就给答案加上 $\sum_{i=w_1+1}^{w_2}L+i$；当遇到和 $(x,c)$ 完全相同的二元组时停下。时间复杂度和 kmp 相同。

注意 kmp 的复杂度是均摊的，即使我们能够存下所有的版本，也不能在扩展新版本时直接由原版本暴力跳 fail link 扩展而来此时有两种做法。

注意到一个字符串 $s$ 的所有 border 构成 $O(\log|s|)$ 段等差数列，我们考虑利用这一性质优化跳 fail link 的过程。具体来说，我们对当前的 $s[1\cdots k]$ 考虑其最长 border，设其为 $k-d$，那么 $d$ 是 $s[1\cdots k]$ 的周期。由弱周期引理，所有 $\le k-d$ 的数中只有 $d$ 的倍数是周期（因为弱周期引理需要 $p+q\le |s|$），这对应着所有长度 $\ge d$ 的位置只有形如 $k-xd$ 的位置是 border（并且进一步由于 $d$ 是周期，这些 border 的下一个字符总是相同的）。

因此我们只需要令 $k\leftarrow k\bmod d+d$，即最小的一个 $\ge d$ 的形如 $k-xd$ 的位置，即可。这里很多地方想要解释 $+d$ 的原因，但实际上注意上面我们的论断都需要弱周期引理那个 $p+q\le |s|$ 的条件，因此只能说明长度 $\ge d$ 的位置中有且仅有 $k-xd$ 这些 border，如果贸然跳到 $k\bmod d$ 就可能会错误地漏掉若干 border。

回到本题。我们上面说过，所有 $\ge d$ 的长度形如 $k-xd$ 的位置均为 border，且这些 border（除了最后一个）后面的字符相同，由于我们需要维护的是前缀最大值，因此这些字符的贡献都被 $k$ 这一位置覆盖，可以直接忽略他们。注意由于最后一个 border 的字符不同，我们需要先小跳一步计算贡献，然后再跳等差数列。因此就可以在不均摊的 $O(\log n)$ 时间内完成跳 fail link 的过程了。只需要把操作离线并建立操作树即可。

Luogu11585 难度 4

• $f(1)$

建笛卡尔树，那么答案一定是选笛卡尔树上的一个矩形。容易做到 $O(n)$。

• $f(2)$

如果两个矩形横坐标区间不交，只需要枚举分界点 $i$，计算在直线 $x=i$ 前后的最大矩形面积，相加即可。

对于相交的情况，两个一定在笛卡尔树上成祖孙关系，考虑如果选了 $u,v$ 这两个点，其中 $u$ 是 $v$ 的祖先，其贡献为 $-len_v\times h_u+len_u\times h_u+len_v\times h_v$。

在祖先处统计，李超树合并维护 $(-len,len\times h)$ 的这些直线即可。

• $f(3)$

对于三个矩形的横坐标区间互不相交的情况，DP 即可。

如果前两个矩形的横坐标区间都和第三个不交，类似 $k=2$ 的两个不交的部分做一遍即可。

设选的三个矩形对应到笛卡尔树上的节点分别为 $u,v,w$。

如果 $u,v,w$ 依次为祖孙关系就只需要把 $k=2$ 的再做一遍。

具体来说我们设 $G_v$ 表示选一个 $v$ 和 $v$ 的子孙 $w$，其 $-len_w\times h_v+len_v\times h_v+len_w\times h_w$ 的最大值，再设 $H_u$ 表示选一个 $u$ 和 $u$ 的子孙 $v$，其 $-len_v\times h_u+len_u\times h_u+G_v$ 的最大值，两个都可以用李超树优化。

剩下的唯一情况是选一个祖先 $u$，然后选两个 $v,w$ 满足 $v,w$ 互不为祖孙关系，造成的贡献为

我们考虑放宽限制，发现当 $u$ 不为 $v,w$ 的祖先时，这个东西不会算的更大。考虑对 $u$ 不做任何限制，只钦定 $v,w$ 不交。那么如果没有不交的限制，我们需要对一个 $(-len_i,len_i\times h_i)$ 这样的东西求一下凸包，然后和自己做闵可夫斯基和。

考虑如何处理不交的限制。对序列建线段树，每个子树变成一个区间 $[l,r]$，考虑两个不交区间 $[l_1,r_1],[l_2,r_2]$，不妨设 $r_1<l_2$，我们在 $\text{LCA}(r_1,l_2)$ 处统计这个贡献。

具体来说，我们对每个线段树节点维护两个凸包 $L,R$，然后对每个区间 $[l,r]$，我们在 $l$ 的所有祖先的 $L$ 凸包里面插入这个点，$r$ 的所有祖先的 $R$ 凸包里面插入这个点，然后我们对每个线段树节点，把他左儿子的 $R$ 凸包和右儿子的 $L$ 凸包做闵可夫斯基和，把得到的这些点放到总的点集里面，最后再对总的点集求一遍凸包。求出这个凸包之后，再枚举 $u$ 计算即可。

实现的时候写成分治的形式可以减小一部分常数。综上，总复杂度 $O(n\log n)$。

LOJ3341 难度 5

分块。设分出来左散块 $A_1$，中间块 $B_1,\cdots,B_k$，右散块 $A_2$。那么贡献有 $A_1\leftarrow A_1$ 即散块对自己，$A_1\leftarrow A_2$ 即散块对散块，$A_i\leftarrow B_j$ 即散块对整块，$B_i\leftarrow B_j(i\neq j)$ 即整块对整块，$B_i\leftarrow B_i$ 即整块自己。当然还有同块的情况。

首先带散块的都好做：我们总能拆成 $O(\sqrt{n})$ 次查询区间 $[l,r]$ 内有多少 $[x,y]$ 中的数这样的询问（下面记这样的查询为查询 $c(l,r,x,y)$），离线下来值域分块平衡复杂度即可。

这部分的时间复杂度为 $O(qB+n\sqrt{n})$。

如果想要空间线性，发现 $A_1\leftarrow B,A_1\leftarrow A_2$ 这样的都可以直接在端点处挂一个区间。

但 $A_1\leftarrow A_1$ 怎么算呢，我们可以把他当作同块，用同块的方法计算。这个我们最后说。

对于整块的情况，首先考虑 $B_i\leftarrow B_i$，发现由于一块内只有 $O(B)$ 个数，我们预处理 $\text{ans}(x,y)$ 表示如果询问的 $u,d$ 在块内排名分别是 $x,y$ 的答案即可。这部分复杂度为 $O(nB+\frac{qn}{B})$。为了找排名还需要处理 $\text{rank}(i,j)$ 表示 $i$ 这个数在 $j$ 块中的排名，这部分也是 $O(nB)$。

然后再考虑 $B_i\leftarrow B_j$。考虑差分成值域 $[1,d]-[1,u-1]-[1,u-1]\times [u,d]$，发现最后一种是好算的：只需要查询 $[l,r]$ 这些块中值在 $[x,y]$ 中的元素个数 $(1\le l,r\le \frac{n}{B})$。

考虑 $[1,u-1]\times [u,d]$ 怎么算，写一下式子，设 $L,R$ 为这些整块的左右边界，$g(l,r,x,y)$ 表示 $l\cdots r$ 这些块中值在 $[x,y]$ 中的元素个数，那么这部分就是

那这样就很容易做到线性空间了。

如果想要空间线性，只需要对每块单独做。

那还需要查询一些块的 $[1,d]$ 的贡献。考虑从小到大加入每个数，并维护 $s_{i,j}$ 表示 $[i,j-1]$ 中的块对第 $j$ 块的答案贡献，那么如果在 $x$ 这个块内插入了一个数，只会把 $s_{i,x}\leftarrow s_{i,x}+\text{cnt}(i,x-1)$，其中 $\text{cnt}(l,r)$ 表示当前 $[l,r]$ 这些块内已经插入了多少个数。$\text{cnt}$ 可以用前缀和维护。

$[l,r]$ 块的答案就是 $\sum_{i=l}^rs_{l,i}$。那这部分复杂度是 $O(\frac{n^2}{B})$，且空间复杂度天然是线性。

对于同块的情况，朴素的想法是直接拆成 $O(\sqrt{n})$ 次查询 $c(l,r,x,y)$，这样就可以过了。

有一个加强版是 Luogu6579，需要线性空间。考虑再分一次块，把这个散块分成长度为 $S$ 的块，每块内直接暴力 $O(S^2)$ 算，块之间就直接加询问，那么这部分的时间复杂度是 $O(\frac{qB}{S}+qBS)$。注意由于暴力的那些块长加起来是 $B$，因此暴力的复杂度是 $O(BS)$ 而非 $O(BS^2)$。

但空间复杂度是 $O(\frac{qB}{S})$，我们可以偷偷调整 $B$ 和 $S$ 的值（不是）并假装他是线性。

于是总的复杂度是 $O((n+q)\sqrt{n})$，空间是（迫真）线性的，实测可以通过 P6579。