杂题.md

QOJ6 玛里苟斯

注意到一个集合的答案等于其线性基的答案。

$k\ge 3$ 暴力，$k=1,2$ 单独考虑。

P6837 QOJ1138 Counting Mushrooms

根号分治，先查出根号个 $0/1$，再一次查询根号个。

精细实现，$2$ 次查 $5$ 个。

QOJ1430 Ineq

Pick 定理数凸包内点数

P8985 QOJ3270 魔塔 OL

贪心部分，前半段 $a_i\le b_i$，按 $a_i$ 升序，后半段按 $b_i$ 降序，反向操作可证。

转化为四维偏序，考虑对于高维偏序的一般做法：用 bitset 处理出落在这个前缀内的所有点的标号，那么一次查询相当于将每个维度对应的 bitset 求交。由于这里需要顺序递推，考虑分块，每块长 $\log$，块内 $2^B$ 处理，复杂度 $O(\frac{(n+q+V)n}{\log n})$。

P8987 QOJ3272 简单数据结构

注意到不降序列操作后仍然不降，且操作是全局的，考虑维护不降序列区间，整体二分可维护。

QOJ4303 New Level

题意：给定一个图和一个染色方案（$1\sim k$），保证相邻两个点颜色不同，找出一个方案满足：

1. 相邻两个点颜色不同。
2. 只保留两点颜色编号差模 $k$ 同余 $1$ 的边后图仍然连通。

将边权设为两点颜色之差，将点权改为到 $1$ 的最短路。正确性易证。

QOJ4891 树上的孤独

题解

QOJ4895 Lovely Dogs

题解

注意到 $f(i)$ 不为 $0$ 有 $f(i)=f(d)f(\frac{i}{d})$，转化为统计子树内质因子个数不超过一定值的 $v$ 的和，容斥后可维护。

P9055 QOJ4900 数列重排

题解

对于一个 $k$，一个区间合法当且仅当 $0\sim k-1$（称为关键数）都出现过，关键数依次排列显然最优：包含任意 $k$ 个关键数的区间均合法。非关键数仅能插到 $k$ 的整数倍位置和末尾。

QOJ4906 球球

题解

分类讨论。用 $S_i$ 和 $T_i$ 分别表示人和分身在 $a_i$ 时另一个可以在的位置集合，几种操作都能简单维护。

QOJ4909 《关于因为与去年互测zjk撞题而不得不改题这回事》

题解

贪心部分，如果当前位为 $1$ 的个数大于等于 $k$，则只保留当前位为 $1$ 的数，答案这一位为 $1$，否则这一位为 $0$。

假设当前序列有序，则只需要判断第 $k$ 大的数，而如果当前位为 $0$，忽略当前位的第 $k$ 大一定在整个序列前 $2k$ 个。所以 $\log v$ 层的前 $k$ 大一定在整个序列前 $k\log v$ 个，取出来暴力即可。

取出链上前 $q$ 大可以每次取最大值后分成两条链。

QOJ4914 Slight Hope

$l$ 限制转为区间查，对 $r$ 分块。注意到一个区间构成的森林中作为根的节点深度相差至多为 $1$，可快速求出一个点所在根节点。

QOJ4924 蜘蛛爬树

题解

分类讨论。发现查询可以在凸包上二分解决。树剖线段树维护凸包，建树时凸包从儿子归并可以少掉排序的 $\log$。

QOJ5040 Dirichlet $k$-th root

题解

当 $f(1)=1$ 时，有 $f=g^{\text{inv}(k)}$。

QOJ5047 Permutation

题解 J

每次按最小值分治。

QOJ5171 理论出线

QOJ5305 Oscar is All You Need

分类讨论。

注意到可以通过 $op(i,2),op(1,i)$ 将末尾数移至第 $i$ 个数后，考虑每次将插入到前面来排序。由于每段非空，显然不能将通过这种方法交换最后两个数，需特殊考虑。

QOJ5308 RPG Pro League

左边四个点分别代表一队中 $4$ 个位置，右边 $7$ 个点表示玩家类型，求出最多多少组对于左部点的完美匹配。考虑完美匹配的判断：Hall 定理（$\mathrm{\forall }S\subseteq X,|N(S)|\ge |S|$），那么能拆分出的完美匹配组数就是 $min(\frac{|N(S)|}{S}),S\subseteq X$。

考虑修改，显然加入/删除 $x$ 后最多只会删除/加入一个人，且这个人为所属类型集合中最大值/集合外最小值，枚举即可。

QOJ5309 Guess Cycle Length

根号做法显然。考虑查询得到的编号一定在 $1$ 到 $n$ 之间，可以通过随机查询一些位置来得到一个较大的下限，然后使用根号做法即可。

QOJ5312 Levenshtein Distance

记 $f_{i,j}$ 表示 $S_{1,x}$ 与 $T_{1,x+j}$ 距离为 $i$，$x$ 最大值，ST 表维护 $\text{LCP}(S_{x,|S|},T_{y,|T|})$，对于 $T$ 每个起始位置 $k^2$ 转移一次即可。

QOJ5418 Color the Tree

法 1：考虑每层分开考虑，对当前层的所有点建虚树后可 dp。

法 2：$f_{x,i}$ 表示 $x$ 子树中第 $i$ 层全部染色的代价，长链剖分可做。

QOJ5421 Factories Once More

记 $f_{x,i}$ 表示 $x$ 子树中选了 $i$ 个点的最大值，转移 $f_{x,i}=max(f_{x,i-j}+f_{y,j}+wj(k-j))$，注意到 $f$ 是上凸函数（上凸函数的 $(max,+)$ 卷积仍为上凸函数）。考虑维护单调的差分数组，$(max,+)$ 卷积为合并两个差分数组，$f_{x,i}\to f_{x,i+1}$ 即在最高点插入一个 $0$，同时还需要支持给差分数组加上等差数列，平衡树启发式合并维护。

QOJ5423 Perfect Matching

转化为一个二分图第 $i$ 条边连接 $a_i-i$ 与 $a_i+i$，问能否将边分成 $\frac{n}{2}$ 对使得每队边有公共点。

对于一个连通块 dfs，通过调整当前点到父亲的边可以使得其余连接到这个点的边均匹配，到父亲的边一定会在父亲点匹配。

QOJ5425 Proposition Composition

分类讨论。

1. 删其中某一条边即不连通。维护未被覆盖的边数即可。
2. 其中一条边覆盖另一条。当且仅当链上的那条边只被一条边覆盖，容易维护。
3. 两条边都在链上。当且仅当所有额外边要么同时覆盖要么同时不覆盖。考虑维护一个集合满足集合内任意两条边满足条件，线段树维护区间内最小前驱/最大后继，暴力分裂，使用启发式分裂（修改分裂后较小的一个集合）维护所属集合。

QOJ5519 Count Hamiltonian Cycles

尽量使前缀中两种点匹配但不能全部匹配，贪心即可。

QOJ5523 Graph Problem With Small $n$

记 $f_i$ 表示以 $1$ 开头经过 $i$ 中的点的路径可能的结束点，容易转移与求答案。

QOJ5528 Least Annoying Constructive Problem

先考虑奇数情况：把所有边分成 $n$ 组，其中第 $i$ 组为 $(i-1,i+1),(i-2,i+2),\dots ,(i-n/2,i+n/2)$（所有数对 $n$ 取模）。依次输出 $1$ 到 $n$ 组中的边即可，容易证明。

偶数情况先去掉 $n$ 按奇数的方法分组，然后每组末尾加上 $(i,n)$，容易证明。

QOJ6308 Magic

注意到 $l,r$ 互不相同，那么对于有交但不包含的两个区间 $[l_1,r_1)$ 与 $[l_2,r_2)$（$l_1<l_2$），要使 $a_{l_1}\ne a_{l_1+1}$，显然 $[l_1,r_1)$ 需要比 $[l_2,r_2)$ 后操作，$r_2$ 同理，即 $l_1$ 与 $r_2$ 至多只能有一个满足条件。

转化为二分图最大独立集，使用 bitset 可以通过。

QOJ6501 Graph Partitioning

对于一条边 $(x,y)$，在第一棵树上时 $x$ 是 $y$ 的父亲，第二棵树上时 $y$ 是 $x$ 的父亲，相当于选择第一棵树的 $x$ 或第二棵树的 $y$，每个点仅能被一条边选择。有解当且仅当每个连通块边数等于点数，即基环树，方案为 $2$。

QOJ6837 AC Automaton

记 $f$ 为 $u$ 子树中某种字符的个数，$g$ 为 $u$ 祖先中某种字符的个数，答案即为 $\sum _{s_u{=}^{\prime }{A}^{\prime }}{f}_{u,‘C^{\prime }{,}^{\prime }{?}^{\prime }}+\sum _{s_u{=}^{\prime }{?}^{\prime }}max(f_{u,‘C^{\prime }{,}^{\prime }{?}^{\prime }}-g_{u,‘A^{\prime }{,}^{\prime }{?}^{\prime }},0)=\sum _{s_u{=}^{\prime }{A}^{\prime }}{F}_u+\sum _{s_u{=}^{\prime }{?}^{\prime }}max(G_u,0)$。考虑维护 $F$ 与 $max(G,0)$。

对询问分块，块内在虚树上处理，容易维护。

QOJ6842 Popcount Words

容易想到建立 AC 自动机后暴力跳。考虑倍增，注意到 $2|\text{popcount}(k)$ 时 $[k{2}^n,(k+1)2^n)$ 与 $[0,2^n)$ 相同，否则恰好相反。记 $w_{n,0/1}$ 表示 $[0,2^n)/[0,2^n)$ 取反，那么任意一个区间可以拆分为 $\log$ 段 $w$。

QOJ6846 Wiring Engineering

确定 $a$ 和 $c$ 后容易 $n^2$ 转移，注意到方程与 $a,c$ 无关，可以转化为 $(a,c)$ 到 $(b+1,d+1)$ 的最长路。注意到 $n$ 较小，$q$ 较大，考虑分治，将两维中左右端点差距较大的一个分治。枚举中点 $m$ 对应的点 $i$，表示 $m$ 左边的点连接 $i$ 左边的点，$m$ 右边的点连接 $i$ 右边的点，容易处理出跨过中点的询问的答案，复杂度 $O(n^3+nq)$。

P9061 QOJ7436 Optimal Ordered Problem Solver

考虑维护轮廓线，使用平衡树维护轮廓线上的点。轮廓线外的点的贡献是坐标与时间的三维偏序，当询问点在轮廓线外时，右上方的区域一定与轮廓线无交，那么分别求出上方、右方、右上方的点数即可，复杂度 $O(n\log n)$。

QOJ7736 Red Black Tree

记 $f_{x,i}$ 表示 $x$ 到其子树内所有叶子黑点个数均为 $i$ 的最小代价，可以证明 $f_x$ 是凸函数，因此可以维护差分数组，$(min,+)$ 卷积只需要合并两个差分数组，当前点的贡献为插入一个 $-1$ 或 $1$，可以用两个 vector 分别维护负数和正数部分。

QOJ7743 Grand Finale

考虑枚举上限和达到上限的时刻，可以直接计算出当前手上每种牌有多少，前后分开考虑。记 $f_{i,j}$ 表示未达到上限时取完前 $i$ 张牌手上有 $j$ 张 $2$，此时手上最多有多少 $1$，$g_{i,j}$ 表示达到上限后要取完 $i\sim n$ 张牌手上有 $j$ 张 $2$，此时手上最少需要多少 $1$，容易转移。

QOJ7754 Rolling For Days

QOJ7905 Ticket to Ride

设 $f_{i,j},g_{i,j}$ 分别表示前 $i$ 条途了 $j$ 条，最后一条涂了/没涂，$h_{i,j}$ 表示 $[i,j]$ 涂完的贡献，有 $f_{i,j}=max(g_{k,j-i+k}+h_{k,i})$，注意到 $i-j=k-(j-i+k)$，即 $f$ 总是从 $i-j$ 相同的 $g$ 转移而来，用线段树维护可以做到 $O(n^2\log )$，用并查集维护可以通过。

QOJ8005 Crossing the Border

按代价排序，设 $f_i$ 为选出 $i$ 中所有物品的最小代价，容易 $3^n$ 转移。考虑将状态改为 $f_{LR}$，$L,R$ 分别表示前一半和后一半的物品是否选择，转移枚举 $L$ 的子集 $L^{\prime }$，$R$ 的超集 $R^{\prime }$，考虑由 $f_{L^{\prime }R}$ 转移到 $f_{L{R}^{\prime }}$。钦定 $L^{\prime }$ 不包含 $L$ 中最靠前的数，那么转移代价即可确定。要保证 $(L\oplus L^{\prime })|(R\oplus R^{\prime })$ 中总大小不超过 $w$，可以考虑 $L^{\prime }$ 按大小总和从小到大排序，$R^{\prime }$ 从大到小排序，双指针扫一遍即可。复杂度 $O(3^{\frac{n}{2}}{2}^{\frac{n}{2}})$。

QOJ8235 Top Cluster

二分答案，转化为判断点权不超过 $mid$ 的点到 $x$ 的最大距离是否不超过 $k$，对于每个前缀处理出直径的两个端点即可。

QOJ8240 Card Game

记 $f_{i,j}$ 表示区间 $[i,j]$ 的答案，$nx{t}_i$ 为 $i$ 之后最小的 $j$ 满足 $a_i=a_j$，那么有

$$
f_{i,j} =
\left { $$\begin{array}{ccc}{f}_{nx{t}_i+1,r}& nx{t}_i\le r{f}_{l+1,r}+1& nx{t}_i>r\end{array}$$ \right.
$$

用可持久化线段树维护 $f_{i,j}$，那么上式即为 $f_{i+1}$ 中 $<nx{t}_i$ 的部分与 $f_{nx{t}_i+1}$ 中 $\ge nx{t}_i$ 的部分拼接起来后对前面部分区间加，容易维护。

QOJ8330 Count off 3

显然只用考虑 $1\sim 6$ 进制，$7$ 进制限制最低位不为 $0$，容易做到 $n{7}^6$。注意 $k$ 进制与 $7-k$ 进制的差别：奇数位取反，偶数位不变。考虑枚举偶数位在 $1,2,3$ 进制下的和，那么奇数位的和在每种进制下都有两种不能出现。上界限制通过枚举卡上界多少位解决。

QOJ8542 Add One 2

尝试考虑将 $b$ 从最终状态减到 $0$，代价显然为 $b_i$ 的和，考虑 $b$ 的限制条件。如果 $b_i>b_{i+1}$，那么至少需要在进行 $b_i-b_{i+1}$ 次 $[1,i]$ 减一的操作，反之亦然。设 $b_0=b_{n+1}=inf$，那么上述条件即 $b_0\ge \sum _{i=0}^{n}max(b_i-b_{i+1},0)$，注意到 $b_i-b_{i+1}$ 加起来等于 $0$，转为化 $\sum _{i=0}^n|b_{i+1}-b_i|\le 2inf$。显然只有将 $a$ 中较低的一段加一才能将总和减少 $2$，用笛卡尔树维护即可。

QOJ8547 Whose Land?

扫描线扫 $r$，每个点 $i$ 记录 $[1,r]$ 中最大的 $j$ 使得 $i$ 与 $j$ 距离不大于 $K$，统计多少个 $j$ 大于等于 $l$ 即可。bfs 后每一层的节点都是连续的，加入一个点时只需要做 $2K+1$ 次区间赋值即可。

QOJ8553 Exchanging Kubic

首先查出每个数的正负，将相邻符号相同的合并。考虑查询相邻三项 +-+，如果结果不小于两个正数较大的就合并这三项，否则说明负数绝对值大于两个正数中较小的。考虑查询最小的正数及其左右两项 +-+-+，对前三项和后三项做上述查询，如果均未合并则表明第三个数小于两个负数的绝对值，可以合并中间三项。

QOJ8554 Bot Friends

容易发现对于一段形如 >>><<< 的序列，满足 > 的个数与 < 的个数相差不超过 $1$，那么可以直接删去并产生 $len-1$ 的贡献。容易 $n^2$ dp。

QOJ8343 玩游戏

题解

考虑用两张牌映射到这 $n$ 个数的和 $s$，首先将每个数减去 $s$，我们希望找到两个和为 $0$ 的牌，这样两个数的和就是 $2s$。两两匹配后共有 $n+1$ 组，显然不可行，考虑将 $(0,1,2n),(2,n,2n-1),(4,n+1,2n-3)$ 组成一组，剩下两两匹配，共 $n-1$ 组，那么至少有两个出现在同一组中。但这样会产生 $6$ 种特殊情况，考虑使用两数的差来区分，调整顺序可以得到任意特殊情况与其他情况差均不相同的方案。

CF1768F Wonderful Jump

如果有 $a_k\le a_i,a_j$，显然 $i\to k,k\to j$ 优于 $i\to j$。即每一步转移区间最小值均在两端。

考虑对每个 $i$ 以 $a_i$ 为最小值向前、向后转移。注意到代价是一次跳过的长度的平方，可以考虑用上界限制转移范围，容易发现长度大于 $\frac{n}{a_i}$ 时一定劣于一步一步跳。

易证复杂度 $O(n\sqrt{n})$。

CF1868D Flower-like Pseudotree

分类讨论。

1. $d_i\ge 2$ 的点有 $n$ 个。
2. $d_i\ge 2$ 的点有 $0$ 个。

以上情况容易构造，剩下的情况考虑把两个 $d_i\ge 3$ 的点组成环（否则显然无解），剩余 $d_i\ge 2$ 的点分别拖两条链。$d_i\ge 2$ 的个数为奇数时需尝试把一个点往尽量浅的位置放，不能则无解。

CF1728F Fishermen

相当于 $i$ 和 $a_i$ 倍数连边后跑最大匹配。直接做是 $O(n^4)$ 的，假如每次成功增广后再清空标记数组可以做到 $O(n^3)$。

UOJ883 景点观光

先删掉子树内无关键点的点，猜测最终路线为以某种顺序遍历整棵树，即答案为 $2(n-1)-k$，$k$ 为最多能进行几次跳两步。

考虑 dp，注意到如果从上一个子树出来与进入下一个子树都是跳一步，那么可以考虑合并这两个操作。记 $f_{x,0/1,0/1}$ 表示遍历完 $x$ 子树（包括进入子树与离开子树），第一个操作是否为跳一步，最后一个操作是否为跳一步。$f_{x,0,1}$ 与 $f_{x,1,0}$ 等价，状态可记为 $g_{x,0/1/2}$。

假设已经知道了每个子节点的决策，可贪心地将其拼在一起。观察发现，一般钦定任意一个子节点更换决策对答案的影响不超过 $1$，那么每个子节点选 $g_{i,j}$ 较大的那一个，如有多个最大值选 $j$ 最大的。唯一一种例外是所有子节点决策均为 $0$，自身决策为 $2$ 时，特判即可。

CF429E Points and Segments

容易想到将染色变为对边定向，即删去覆盖次数为偶数的边后每个连通块跑欧拉回路。

CF1973F Maximum GCD Sum Queries

钦定不交换 $a_1,b_1$，那么两个序列 $gcd$ 分别是 $a_1,b_1$ 的因数，注意到 ${10}^8$ 内一个数的因数个数最大不超过 $1000$，考虑以 $(\underset{1}{gcd},\underset{2}{gcd})$ 为状态。

记 $f_{p_1,p_2}$ 表示最终结果为 $(p_1,p_2)$ 时 $[2,n]$ 中可以满足的 $i$ 的个数（即 $a_i,b_i$ 分别是 $p_1,p_2$ 或 $p_2,p_1$ 的倍数），考虑通过类似高位前缀和的方式转移，只需要在 $f_{gcd(a_1,a_i),gcd(b_1,b_i)}$ 与 $f_{gcd(a_1,b_i),gcd(b_1,a_i)}$ 处分别 $+1$，在这两个的 $gcd$ 处 $-1$ 避免重复即可。如果 $f_{i,j}=n-1$ 则表示 $(i,j)$ 合法，而代价可以用相同的方式转移。

QOJ5034 >.<

考虑将 $k$ 条路径和 $n$ 个单点建 AC 自动机，标记每条路径的结尾点不能走，答案即为 $1$ 到 $n$ 的最短路。一个点可能在 AC 自动机上出现很多次，直接做是 $O(n^2)$ 的。由于出边是继承自 fail 的，只有在当前点存在该儿子时被修改，所以会存在大量的点的某一个出边指向同一个点，并且这些边对应原图中的同一条边，在跑 dij 时显然只用更新一次。考虑可持久化，每个点继承 fail 的线段树，然后将当前点存在的儿子在线段树上新建节点，跑最短路时每次访问过的点直接删除。注意 $1\sim n$ 单点的每个儿子需单独建点，以区分不同的边。

QOJ5015 树

容易想到确定一个根后分层，相邻两层确定连边。假设要确定 $A$ 到 $B$ 的连边，注意到 $B$ 中一点到 $P\subseteq A$ 的距离等于其父亲到 $P$ 的距离加 $|P|$，考虑随机平分 $A$ 得到 $P$ 后分治，可以证明 $P$ 是 $A$ 中任意一个等价类大小不超过 $\frac{|A|}{2}$，并且由于随机无法卡满。

QOJ5016 Range Minimum Element

称 $a$ 最终得到的 $b$ 为 $F(a)$。考虑以下过程：对于一个数组 $b$，从小到大枚举 $x$，对于所有 $b_i>x$ 有 $a_{l_i\sim r_i}>x$，将 $a$ 中没有被限制且没有被填的位置填入 $x$，最终得到的 $a$ 记为 $G(b)$。显然有 $F(G(b))=b$，即 $b$ 和 $G(b)$ 一一对应，考虑统计合法的 $G(b)$ 的个数。

记 $f_{i,j,k}$ 表示 $[i,j]$ 中填入 $[c-k+1,c]$ 合法的方案，转移枚举 $l$ 为第一个 $k$ 的位置，有 $f_{i,j,k}\leftarrow f_{i,l-1,k-1}{f}_{l+1,j,k}$，显然 $[i,l-1]$ 需合法。整个区间合法时再加上不填 $k$ 的方案。$f_{1,n,c}$ 即为答案。注意到 $f$ 为关于 $c$ 的 $n$ 次多项式，求出 $c\in [0,n]$ 的答案后拉插即可。

CF1967D Long Way to be Non-decreasing

二分答案，从前往后每个数选择基环树上 $mid$ 步能到达的点中最小的点，双指针扫描即可。

CF1967E2 Again Counting Arrays (Hard Version)

考虑对于一个确定的 $a$ 如何构造 $b$，容易发现能 $+1$ 就 $+1$ 是不劣的，不难证明。转化为统计路径，每一步向右移动一格，向上或向下移动一格。可以直接反射容斥，注意可能终点不在 $[0,m]$ 之间，容斥时钦定经过一次上边界即可。

QOJ5019 整数

从高位到低位做，记 $f_i$ 表示第 $j$ 个数是否贴上限的答案，容易 $3^n$ 转移。考虑使用 FWT 优化，$f_i$ 中 $i$ 的第 $j$ 位为 $0/1$ 表示不贴上限/贴上限，$g_i$ 中 $i$ 的第 $j$ 位表示第 $j$ 个数的当前位，根据 $R_i$ 当前位的不同有两种转移：

• $R_i$ 当前位为 $0$：$f_0(g_0+g_1)\to f_0,f_1{g}_0\to f_1$。
• $R_i$ 当前位为 $1$：$f_0(g_0+g_1)+f_1{g}_0\to f_0,f_1{g}_1\to f_1$。

对于第一个转移，设 $h_0=g_0+g_1,h_1=g_0$，那么转移即为 $f_i=f_i{h}_i$。

对于第二个转移，显然是按位与卷积，使用 FWT 解决。

将两种转移合在一起，FWT 时仅操作 $R_i$ 当前位为 $1$ 的位即可。

CF1975F Set

枚举 $S$ 每一位，显然当枚举到第 $i$ 位时，剩下的 $T$ 只剩 $2^{n-x}$ 种，枚举 $T$ 并更新即可。

CF1943D2 Counting Is Fun (Hard Version)

不难发现，合法当且仅当 $a_i\le a_{i-1}+a_{i+1}$。容斥，钦定多少个 $i$ 不满足，dp 即可。

CF1943E2 MEX Game 2 (Hard Version)

二分答案，设 $f_i$ 为 $i$ 的个数，显然 Alice 的策略为每次取 $f$ 最小的一个。枚举 Bob 最后要删空的数 $x$，由于 Alice 总是取当前最少的数，所以比 $x$ 多的数显然不用管，而 Bob 需要保证 $x$ 始终是剩余数中最大的，那么其策略即为每次将一个后缀减少到“几乎相等”（即极差不超过 $1$）。我们可以找到所有数“几乎相等”的时刻，可以通过二分解决。此后的情况容易处理。

CF1943F Minimum Hamming Distance

钦定 $t$ 中 $0$ 为众数，否则翻转 $s,t$ 即可。对于 $s_i=0$，显然有 $[1,n]$ 满足条件。设一个区间的权值为 $1$ 减 $0$ 的个数，对于 $s_i=1$，满足条件当且仅当一个包含 $i$ 的区间权值大于等于 $0$，显然 $i$ 为这个区间的端点之一。记 $f_{i,j}$ 表示枚举到前 $i$ 个数，$[1,i]$ 后缀最大权值为 $j$，第一种容易转移，第二种枚举右端点，显然翻转 $0$ 需尽量靠后，容易转移。

CF1948F Rare Coins

转化为 $x$ 个银币比 $y$ 个银币价值多 $k$ 的方案数，为 $\sum _d\sum _i(\genfrac{}{}{0ex}{}{x}{d+i})(\genfrac{}{}{0ex}{}{y}{i})=\sum _d(\genfrac{}{}{0ex}{}{x+y}{y+d})$，注意到 $x+y$ 为总共银币数量不会改变，预处理即可。

CF1936D Bitwise Paradox

注意到 $v$ 是固定的，考虑线段树上维护前后缀每个 $b$ 的或和对应的 $a$ 的最大值，显然前后缀不同的或分别只有 $\log$ 种，容易维护。

CF838F Expected Earnings

记 $f_{i,j},g_{i,j}$ 分别表示取了 $i$ 个球其中 $j$ 个红球后最大期望收益和下一个是红球的概率，有转移：$f_{i,j}=max((f_{i+1,j+1}+1)g_{i,j}+f_{i+1,j}(1-g_{i,j}),0)$。考虑求 $g_{i,j}$，记 $h_{i,j}$ 为取 $i$ 个球其中 $j$ 个红球的概率，容易发现有 $g_{i,j}=\frac{h_{i+1,j+1}}{h_{i,j}}\times \frac{j+1}{i+1}$，$h_{i,j}=\frac{j+1}{i+1}{h}_{i+1,j+1}+\frac{i+1-j}{i+1}{h}_{i+1,j}$。

CF1060G Balls and Pockets

首先删除 $a_1$ 之前的数。对于一个极大的数 $x$，显然 $x+n$ 操作一次后会移动到 $x$，即 $x$ 与 $x+n$ 在同一个 $a_i$ 处被删除，容易得到 $[x,x+n-1]$ 被最终删除的位置互不相同，考虑维护这么一个长为 $n$ 的区间。假如当前区间覆盖到了 $w$ 个 $a$，那么把这些位置从区间中删去，剩下的位置向前移动，不难发现得到的区间恰好与当前区间相邻，长度减少 $w$。那么对于一个位于第 $i$ 个区间数 $j$ 的询问，其答案即为第 $i-k$ 个区间数 $j$ 位置对应的数。

CF1930E 2..3…4…. Wonderful! Wonderful!

显然删去的数个数必须是 $2k$ 的倍数，可以对于每个 $k$ 直接枚举。显然任意一个保留的数左右两侧至少有 $k$ 个删除的数，那么合法的必要条件为前 $k$ 个和后 $k$ 个被删除，可以证明这是充分的，容易组合数计算。

CF1930F Maximize the Difference0

从高到低位做，显然每次尽量让较大的数当前位为 $1$，较小的数当前位为 $0$ 最优，即查询是否存在 $a_i$ 是 $x$ 的子集、超集，由于只查询是否存在，每次暴力 dfs，当前数已存在就退出即可。

CF1930G Prefix Max Set Counting

将一个点儿子按子树内最大编号排序，显然一个子树内的点不会受到其后子树内点的影响，以这个顺序 dfs，那么一个点只可能受到 dfs 序小于自己且编号小于自己的点的贡献。

令 $f_x$ 表示 $x$ 结尾且为前缀最大值的方案，$g_x$ 为 $x$ 子树内最大点，dfs 到点 $x$ 时，依次遍历其儿子 $i$ 并将 $f_i$ 贡献到树状数组上的位置 $g_i$，遍历完成后移除贡献。计算 $f_x$ 时注意其祖先都是必选的，显然转移点不能小于其祖先最大值。

CF1930H Interactive Mex Tree

转化为查询路径外点的 $min$。按照 dfs 时进栈的顺序和出栈的顺序，可以将一条路径外的所有点划分成五个区间。

QOJ4805 Grammy Sorting

题解 双极定向

考虑维护一个合法的子图然后依次加入点，构造双极定向，按照拓扑序倒着考虑每个点。现在有一个包含 $B$ 的子图 $G$，$G$ 内每个点到 $B$ 的路径权值递增，考虑加入一个点 $x$，找到 $x$ 权值最小的后继 $v$：

• 当 $p_A<p_v$ 时，操作 $A$ 到 $x$ 的路径。
• 当 $p_A>p_v$ 时，将 $v$ 加入操作路径，并找到 $v$ 的最小后继作为新的 $v$。重复以上步骤直到 $p_A<p_v$ 或者 $v=B$，操作后新的子图显然合法。

QOJ5022 【模板】线段树

可以转化为 $n\times m$ 的网格，每个格子向上连边，第 $i-1$ 行 $[l_i,r_i-1]$ 的格子向右上方连边。考虑在 $m$ 这一维上分块，对于每一块，将块内出现的每个 $l,r,pos$ 设为关键点，考虑每一段内的转移，显然未出现斜向边的行是无用的，容易处理。

现在知道一个 $w\times h$ 左侧和下侧所有点的答案，要求上侧和右侧所有点的答案，分类讨论：

• $(s,0)\to (w,t):(\genfrac{}{}{0ex}{}{t}{w-s})$
• $(s,0)\to (t,h):(\genfrac{}{}{0ex}{}{h}{t-s})$
• $(0,s)\to (t,h):(\genfrac{}{}{0ex}{}{h-s}{t})$
• $(0,s)\to (w,t):(\genfrac{}{}{0ex}{}{t-s}{w})$

显然对于方案为奇数的转移才有效，而 $(\genfrac{}{}{0ex}{}{n}{m})\equiv 1mod2$ 当且仅当 $n\text{and}m=m$，上面四种均可在 $max(h,w)\log$ 的时间解决。总复杂度 $O(n\sqrt{n}\log n)$。

QOJ5029 在路上

考虑链的情况，考虑 nth_element，需要快速判断两个数在链上的位置关系。容易想到询问这两个点与链的一个左端点，得到的点即较左的那一个。找端点只需要三个数不断舍弃中间那个即可。

考虑树的情况，注意到重心每个子树大小不超过 $\frac{n}{2}$，也就是随机一对点在重心同一子树内的概率不超过一半，那么随机一对点并假设重心在这条链上，期望 $2$ 次得到答案。

考虑随机链上一个点并取其大小超过 $\frac{n}{2}$ 的儿子，不存在此点即为重心。但是相较于链上的情况这种情况每个点带点权，在链上均匀随机复杂度退化到 $O(n\log n)$，考虑带权随机，注意到随机 $1\sim n$ 的一个点后找到其在链上的祖先等价于带权随机链上一点。找到 $x$ 的链上祖先只需要遍历链上的点不断令 $fa=ask(x,fa,i)$，其中 $fa$ 为当前答案，$i$ 为枚举的链上的点。考虑如何找到一个点 $x$ 大小大于 $\frac{n}{2}$ 的儿子或判断不存在，通过 $ask(x,u,v)$ 可以判断 $u$ 和 $v$ 是否在同一子树内，考虑用摩尔投票求出绝对众数即可。

QOJ5013 Astral Birth

钦定划分出的一段可以为空，容易发现一个连续段总是不会被划分成两个部分，将整个序列缩为 $01$ 交替的序列。考虑共 $k$ 个连续段的序列最少需要分多少段可以变得有序，注意到当存在一个 $0$ 在 $1$ 前面时这两个段可以划为一段，总共 $k-1$ 段，否则至少 $k$ 段，注意到 $k\ge 3$ 时一定可以达到 $k-1$，剩下情况特殊考虑。

现在需要选一些连续段使得拼起来后连续段个数不超过 $m$，选出来的最大长度和贡献到 $max(m-1,2)$ 的答案。容易发现删掉相邻两个连续段一定劣于删掉其中一个，即删掉的连续段不相邻。在不相邻的情况下删掉中间的会使连续段个数减少 $2$，删掉两侧的减少 $1$。由于要求不相邻，那么两侧分别最多删一个区间，每一种情况做一遍后面的过程即可。而中间的情况容易用反悔贪心解决，每次选最短的连续段 $i$，删除 $i,l_i,r_i$ 并将 $a_{l_i}+a_{r_i}-a_i$ 作为新的连续段加入。

CF1909I Short Permutation Problem

枚举 $m$，当 $m$ 为偶数时，将 $\ge \frac{m}{2}$ 的成为大数，其余为小数，将 $1\sim n$ 排成形如 $\frac{m}{2},\frac{m}{2}-1,\frac{m}{2},\frac{m}{2}-2,\cdots ,1,m,\cdots ,n$ 的序列，依次插入，容易发现每次插入大数后这个数和其左右的数形成的数对都满足条件，小数反之。考虑 dp，记 $f_{i,j}$ 表示前 $i$ 个数有 $j$ 对满足条件，容易转移。$m$ 为奇数同理。

容易发现对于不同的 $m$ 均由一段大小数交替和一段大数构成，前面可以直接在 $f$ 上查询，考虑后面部分的贡献。设已经放了前面部分共 $p$ 个数，共 $q$ 对合法，后面部分共 $k$ 个数。每个数插入到一对合法数对中间或开头结尾会产生 $1$ 的贡献，否则产生 $2$ 的贡献，枚举 $i$ 表示产生 $2$ 的贡献的个数，有 $an{s}_{q+k+i}\leftarrow k!f_{p,q}(\genfrac{}{}{0ex}{}{p-q-1}{i})(\genfrac{}{}{0ex}{}{k+q+1}{k-i})$，拆开整理得到 $an{s}_{q+k+i}(p-1-(q+i))!((q+i)+1)!\leftarrow k!\frac{f_{p,q}(p-q-1)!(k+q+1)!}{i!(k-i)!}$，发现为 $P\leftarrow k!\frac{Q}{I}$，其中 $p,k$ 固定，$P$ 仅与 $q+i$ 有关，$Q$ 仅与 $q$ 有关，$I$ 仅与 $i$ 有关，为加法卷积的形式，NTT 即可。

CF1924E Paper Cutting Again

考虑把每条线在结束前被选中的概率加起来。枚举切的哪条线，假设是 $x=i$，那么只需要这条线在 $x=1\sim i-1$ 和 $y=1\sim \lfloor \frac{k}{i}\rfloor$ 之前被选即可。

CF1924F Anti-Proxy Attendance

容易想到在三部分中排除一部分，假设回复无人缺席为 $0$，有人缺席为 $1$，分类讨论，发现无法在三次询问内排除一部分，但四次询问会超出限制。注意到四次询问的情况一定不会排除中间的部分，那么将中间部分取小一点即可，dp 或者按比例分。

CF1889D Game of Stacks

每个点向栈顶连边，会形成一棵内向基环树，注意到不管任意时刻走进这个环，一定会绕着环走一圈并回到起始点，相当于把所有在环上的点弹栈，新形成的图仍然是基环树，所以只需要不断删掉环直到不存在环，每棵树的根节点即为答案。

CF1817F Entangled Substrings

显然 $ac$ 和 $b$ 出现位置的差分数组是相同的，一个字符串 $S$ 的子串的出现位置集合只有 $O(n)$ 种，使用 SA 或 SAM 求出每种出现位置的集合，用哈希将差分数组相同分在一组。对于每一组，出现位置集合相同的字符串显然由若干个 $x_i$ 开头长度为 $[l_i,r_i]$ 的字符串组成。考虑两种字符串 $i,j(x_i<x_j)$ 的贡献：由于两个字符串要恰好拼接在一起，所以必须满足 $x_j-x_i\in [l_i,r_i]$，方案为 $(r_j-l_j+1)(x_j-x_i-l_i+1)$，排序后二分即可。

UOJ577 打击复读

建 SAM，令 $[l_x,r_x]$ 表示 SAM 上 $x$ 节点的最小、最大长度，那么节点 $x$ 的贡献为：

$$|endpo{s}_x|\left(\sum _{i\in endpo{s}_x}w{r}_i\right)\left(\sum _{i\in endpo{s}_x}\sum _{j=l_x}^{r_x}w{l}_{i-j+1}\right)$$

后面部分用后缀和拆开，那么现在要求 $\sum _{i\in endpo{s}_x}w{l}_{i-p+1}^{\prime }$ 其中 $p=l_x-1,r_x$，$p=r_x$ 时上式等于字符串 $[i-r_x+1,i]$ 左权值和，$p=l_x-1$ 时长度为 $l_x-1$ 的字符串的 $endpos$ 与 $endpo{s}_x$ 不同，用字符串 $[i-l_x+1,i]$ 的左端点前一个点的权值之和即可。倍增找到一个字符串对应的节点。由于只会修改 $wl$，考虑将整个字符串翻转变为修改 $wr$，注意到修改一个 $wr$ 仅会影响对应节点到根的一条链，容易统计答案的变化量。

CF1919G Tree LGM

考虑根不同有什么影响，相当于在转移时移除了根所在的子树。可以发现当 $s_{x,x}=0$ 表示对于 $x$ 的所有儿子 $i$ 有 $s_{x,i}=1$，此时显然有 $s_{1\sim n,x}=0$。否则表示存在一个 $i$ 使得 $s_{x,i}=0$，如果这样的 $i$ 超过两个，那么移除任意子树都没有影响，即 $s_{1\sim n,x}=1$。

否则按照 $s_{i,x}=0/1$ 分成两个集合 $S,T$，显然 $T$ 是 $x$ 的一棵子树，考虑找出这个子树内与 $x$ 相连的点 $y$，首先由 $s_{y,x}=0$ 可以推出 $s_{i,y}=1,i\in T$，即 $y$ 出发总是可以到达必败点 $x$，可以证明此条件是充要的。

找到 $y$ 后还需验证合法性才可分治求解，对于一对 $i\in S,j\in T(i\ne x,j\ne y)$，有 $s_{i,j}=s_{y,j},s_{j,i}=s_{j,v}$。

当找不到满足上述条件的 $x$ 时，即对于任意一个 $x$ 删除任意子树均不会影响答案，即任意 $i$ 满足 $s_{i,x}=s_{x,x}$，按 $s_{x,x}=0/1$ 分成两种点，显然每个 $1$ 类点至少连接两个 $0$ 类点，最优方案为一条左右为 $0$，$0,1$ 交错的链，$0$ 多了直接连到 $1$ 上，$1$ 多了无解。

CF1919H Tree Diameter

钦定 $1$ 为根，先用操作 $2$ 分层，对于每一层尝试求出与上一层的连边。假设 $1$ 是叶子，那么将 $t-1$ 层第 $i$ 条边权值设为 $i$，当前层的边 $x$ 和根设为 ${10}^9$，其余边设为 ${10}^5$，那么直径一定经过跟和 $x$，将直径对 ${10}^5$ 取模即可知道经过 $t-1$ 层的边的权值。

当 $1$ 不是叶子时，考虑对于第 $t$ 层考虑将 $t-1$ 层第 $i$ 条边权值设为 $i$，当前层两条边 $x,y$ 设为 ${10}^9$，那么直径一定经过 $x,y$，可以知道经过 $t-1$ 层两条边的权值和。将 $t$ 层每条边 $i$ 和第 $1$ 条边（设为 $o$）做上述过程得到 $f_i$（如果 $o$ 和 $i$ 父亲相同则为 $0$），显然两个数 $f$ 相同表示其父亲相同。我们钦定前 $t-1$ 层任意一个节点均有至少一个儿子，否则即找到一个叶子，用先前做法即可。分类讨论：

• 不同的 $f$ 个数 $\ge 3$。此时只需要任意找两条边 $x,y$ 使得 $o,x,y$ 三条边父亲均不相同，查询 $x,y$，即可知道 $o$ 的父亲。
• 不同的 $f$ 个数 $=1$。
  • $t-1$ 层点数为 $1$。直接连即可
  • $t-1$ 层点数为 $2$。此时图一定是一条链，任意连边均同构，并且一定产生了一个叶子。
  • $t-1$ 层点数大于等于 $3$。将 $o$ 和 $t-1$ 层任意三条边依次设为 ${10}^9$ 查询三次，得到的众数一定是 $o$ 的父亲，并且一定产生一个叶子。
• 不同的 $f$ 个数为 $2$。
  • $t-1$ 层点数为 $2$。此时图一定是一条链，任意连均同构。
  • $t-1$ 层点数大于等于 $3$。将 $o$、$t$ 层另一点 $x$ 与 $t-1$ 层一点 $p$ 设为 ${10}^9$，如果结果超过 $3\times {10}^9$，那么经过的边 $z$ 与 $p$ 一定分别是 $o,x$ 的父亲，$t-1$ 层任意非 $z,p$ 的点均为叶子，否则 $p$ 为叶子。确定根后再用一次操作确定 $o,p$ 父亲即可。

CF1842H Tenzing and Random Real Numbers

考虑将 $1$ 消掉，每个 $x$ 在 $[-0.5,0.5]$ 中均匀随机，条件变为 $x_i+x_j\le 0$ 和 $x_i+x_j\ge 0$。显然 $x_i+x_j$ 的正反由绝对值较大的一个数的正负决定，考虑按绝对值从小到大将 $x$ 加入集合，第一种条件可以转换为当 $x_i\ge 0$ 一定有 $|x_j|\ge |x_i|$，也就是 $j$ 在 $i$ 后加入集合，第二种同理，容易 $2^{n}n$ dp。

CF1984E Shuffle

先忽略根为叶子的情况，考虑相邻两个点，显然其中一个是另一个的祖先，即两个相邻的点最多有一个叶子。考虑找到最大独立集，容易构造叶子集合为最大独立集的方案，即答案为最大独立集。当根为叶子时，答案为根删去后最大独立集 $+1$，换根 dp 即可。

CF1984F Reconstruction

钦定 $s_0=\text{P},s_{n+1}=\text{S},b_0=b_{n+1}=0$，设 $k=\sum a_i$，大胆猜测，合法当且仅当满足：

• 对于 $s_i=\text{P}$，有 $\text{abs}(b_i)\le i\times m$，对于 $s_i=\text{S}$，有 $\text{abs}(b_i)\le (n-i+1)\times m$。
• 对于 $s_i=s_{i+1}$，有 $\text{abs}(b_i-b_{i+1})\le m$。
• 对于 $s_i=\text{P},s_{i+1}=\text{S}$，有 $b_i+b_{i+1}=k$。
• 对于 $s_i=\text{S},s_{i+1}=\text{P}$，有 $\text{abs}(b_i+b_{i+1}-k)\le 2m$。

容易证明以上条件是充分的。注意到一定存在 $i$ 使得 $s_i=\text{P},s_{i+1}=\text{S}$，那么枚举 $k=b_i+b_{i+1}$ 即可。

CF1984G Magic Trick II

猜测 $k$ 为 $n$ 减一个常数，容易发现当 $k=n$ 时，$a$ 必然有序，$k=n-1$ 时，$a$ 为 $1,2,\cdots ,n$ 的循环位移。

考虑 $k=n-2$ 的情况，考虑将 $a$ 拼成一个环，并记录分界点。那么任意操作等价于以下两种之一：

1. 将分界点左移/右移 $2$ 格。
2. 交换分界点左右两侧的数并将分界点左移/右移 $1$ 格。

容易想到枚举 $i=n\sim 1$，通过 $1$ 操作移动到 $i$ 右侧再通过 $2$ 操作将 $i$ 归位，当 $n$ 为奇数时成立，$n$ 为偶数时可能出现无法通过 $1$ 操作移动到 $i$ 右侧。注意到 $n$ 为偶数时每次操作 $n-2$ 个数不会改变逆序对奇偶性，因此分情况考虑：

1. 当逆序对个数为偶数时，按奇数情况做。当出现分界线位置与 $i$ 位置奇偶性不同时，先移动到 $i$ 左侧，将 $i$ 移动到 $1$，然后交换 $a_2,a_3$ 来改变分界线奇偶，可以证明逆序对个数为偶数时是可行的。
2. 当逆序对个数为奇数时，考虑 $k=n-3$，将 $n$ 移到末尾后解决 $n-1$ 的子问题即可。

CF1874E Jellyfish and Hack

设 $f_{i,j}$ 表示长度为 $i$ 的排列需要操作 $j$ 的方案，枚举第一个数的值，容易做到 $n^6$ dp。不难发现答案为 $O(n^2)$ 次的多项式，拉插即可。

CF1874F Jellyfish and OEIS

将 $p_l,\dots ,p_r=l,\dots ,r$ 的区间称为好的，容易发现对于两个相交但不包含的好区间 $[l_1,r_1],[l_2,r_2](l_1<l_2)$，区间 $[l_1,l_2-1],[l_2,r_1],[r_1+1,r_2]$ 都是好的。考虑容斥，由上面的结论，只考虑容斥的区间相交或包含即可不重不漏。记 $f_{i,j}$ 表示只考虑 $[i,j]$ 中的区间的方案和，用 $g_{i,j,k}$ 表示只考虑 $[i,j]$ 中的区间，未被任何区间包含的数有 $k$个，除去未被包含数的方案和来辅助转移，$g$ 转移到 $f$ 时乘上 $k!$ 即可。

CF1608F MEX counting

设 $f_{i,j,k}$ 表示考虑前 $i$ 个数，$\text{mex}=k$，$>k$ 的数有 $j$ 种，这 $j$ 种数具体的值不方便记录，可以先不确定等到移动 $\text{mex}$ 时再确定，。当下一个数 $p\ne k$ 时，$\text{mex}$ 不变，有以下几种转移：

• $p<k$，$k\times f_{i,j,k}\to f_{i+1,j,k}$。
• $p>k$ 且 $p$ 属于出现过的 $j$ 种数中的一种，$j\times f_{i,j,k}\to f_{i+1,j,k}$。
• $p>k$ 且 $p$ 未出现过，$f_{i,j,k}\to f_{i+1,j+1,k}$。

当 $p=k$ 时，考虑枚举 $t$ 表示 $[p+1,t-1]$ 中的数全部出现过且 $t$ 未出现，那么有 $A_j^{t-p-1}\times f_{i,j,k}\to f_{i+1,j-(t-k-1),t}$，展开得到 $\frac{j!}{(j-(t-k-1))!}\times f_{i,j,k}\to f_{i+1,j-(t-k-1),t}$。

容易发现对于每个 $i$，$k$ 这一维合法的状态仅有 $O(k)$ 种，复杂度 $O(n^{2}k)$

CF1844G Tree Weights

令 $1$ 为根，$de{p}_i$ 表示 $i$ 的深度，显然有 $d_i=de{p}_i+de{p}_{i+1}-2de{p}_{lca(i,i+1)}$，考虑去掉最后一项，容易发现将整个式子模 $2$ 后，变成 $d_i\equiv de{p}_i+de{p}_{i+1}(\mathrm{mod}2)$，可以递推得到 $de{p}_{i}mod2$ 的值。考虑将模数变为 $4$，容易发现只需要知道 $de{p}_{lca(i,i+1)}mod2$ 的值即可递推，而这个值在上一轮已经求出，倍增直到模数大于 $nV$ 即可。

CF1976F Remove Bridges

由于 $1$ 的度数为 $1$，显然第一次添加的边一端必须是 $1$，另一端显然是叶子。考虑贪心地把树划成一些祖先 $-$ 后代链使得按长度降序排序后字典序最大，即对于每个点加入其所有儿子所在链中最长的链。假设当前已经不是割边的边为一些链的并集，此时选择两条最长的未被选择的链并将其对应叶子连接在一起显然是合法的且最优的，而连接之后已经不是割边的边仍然为一些链的并集。也就是最开始连接 $1$ 和其所在链对应儿子后每次会选择长度最大的两条链，且因为 $1$ 所在链是所有链最长的，所以这种方案一定最优。

CF1923F Shrink-Reverse

显然最多只会翻转一次。假如不进行翻转操作，尽量将前面的 $1$ 扔到后面即可。进行一次翻转操作，记操作后第一个 $1$ 的位置为 $l$，最后一个 $1$ 的位置为 $r$，得到的数即为 $[l,r]$ 翻转后的结果，显然首先需要最小化区间长度，再最小化 $[l,r]$ 翻转后的字典序。一个区间合法当且仅当 $r-l+1$ 大于等于 $1$ 的个数且不在 $[l,r]$ 的 $1$ 的个数不超过 $k-1$，双指针扫描可以得到最小长度。显然区间外的 $1$ 会填入翻转后区间的一个后缀，不难发现任意两个区间在后缀填入相同数量的 $1$ 后大小关系不变，此时只需要找到合法的 $O(n)$ 个区间中字典序最小的一个，二分哈希或后缀排序即可。

QOJ8518 Roars III

固定根之后，容易发现最优策略即为维护关键点集合，当前点不为关键点时将最远的关键点移动到当前点。考虑如何将根从 $x$ 移动到 $y$，注意到“移动关键点”这个操作是可逆的，考虑用线段树维护以 $x$ 为根时 dfs 序为 $i$ 的点（不包含 $x$）的深度（不为关键点深度为 $-inf$）。换根到 $y$ 只需要将移动到 $y$ 的点撤回，将新的最优点移到 $x$，然后区间加减即可。

CF700E Cool Slogans

考虑建 SAM，注意到钦定 $s_i$ 是 $s_{i+1}$ 的后缀显然不劣，容易想到在 parent 树上从上到下 dp。由于同一个点的字符串 $endpos$ 集合是相同的，所以对于每个点只需要考虑其最长的串。如何判断一个点 $x$ 代表的串是否在其后代 $y$ 中出现至少两次，即判断 $endpo{s}_y\cap [po{s}_x-le{n}_x+le{n}_y,po{s}_x-1]$ 是否为空。可以对于每个点找到最近能转移的祖先转移，也可以记录二元组 $(x,w)$ 表示以 $x$ 结尾答案为 $w$，显然在 $w$ 尽量大的情况下使得 $x$ 深度尽量小即可。

CF1896F Bracket Xoring

容易发现相邻两个位置填 () 时这两个位置的数的异或一定不变，填 (( 或 )) 时一定改变，那么用这种方法可以使 $a_{2i+1}=a_{2i+2}$，构造出来不合法显然无解。在 $a_{2i+1}=a_{2i+2}$ 的情况下，通过填入 () 或 )( 可以使对应的两个数均变为和 $a_1$ 相等，为了合法开头和结尾两个分别填入 (( 和 ))。此时有 $a_1\ne a_2,a_{2n-1}\ne a_{2n}$，可以通过 ((()()...())) 来调整。注意到每次操作均会改变 $a_1$ 和 $a_{2n}$，所以初始必然有 $a_1=a_{2n}$，否则无解。剩下的情况一定所有数均相同，如果全为 $1$ 通过 ()()...()() 调整即可。

QOJ8522 Waterfall Matrix

容易想到对分界线 dp，枚举 $i$，dp 找到在分界线左侧 $<i$ 的数加分界线右侧 $\ge i$ 的数最小的方案，答案即为每个 $i$ 贡献的和。不难发现 $i-1$ 的最优分界线一定在 $i$ 右下，考虑分治，对于 $mid$ 求出答案后分别递归两侧。

考虑对于 $k$ 个点如何快速求答案，我们需要维护一个不降序列 $f$，操作为前缀或后缀 $+1$，然后将每个数设为其后缀最小值。考虑使用 multiset 维护差分，集合中元素 $i$ 有 $j$ 个表示 $f_i-f_{i-1}=j$，后缀 $[i,n]$ $+1$ 直接插入 $i$，前缀 $[1,i]$ $+1$ 插入 $0$ 然后找到集合中最大的 $\le i$ 的数然后删去即可。

QOJ8523 Puzzle II

考虑将较少的一种球移到对面，考虑用两次操作将两个序列中指定的球交换（相对位置可能变化），不难发现有：

aaaaax      ybbbbx      yaaaaa
ybbbb       aaaaa       bbbbx

其中 $a$ 有 $k$ 个，$b$ 有 $k-1$ 个，容易通过这种方法构造方案。考虑如何维护操作后的序列，使用两个 deque 维护这两个区间，每次操作均可直接维护。

QOJ8525 Mercenaries

将 $(S_i,M_i)$ 视为坐标系上的点，那么合法条件即为在一条直线右上，考虑维护凸包，加入一条边的贡献显然是闵可夫斯基和。用线段树维护一个区间的雇佣兵和商品的凸包，线段树二分即可，将询问按斜率排序后每个凸包记录一个指针扫描可以做到单 $\log$。

QOJ8526 Polygon II

转化题意为求最大的数不超过其他数之和的概率。记 $n-1$ 个数的和减去剩下的数的差为 $S$，考虑求出 $S<0$ 的概率，在二进制下按位考虑，设 $b_i$ 表示有多少个 $a_j\ge i$，$f_{i,j}$ 确定前 $i-1$ 位，上一位进位为 $j-1$。由于 $b_i$ 个数每个数等概率选择 $0$ 和 $1$，那么对 $S$ 当前位的贡献为 $b_i$ 个 $0/1$ 的和减一，枚举有其中有 $k$ 个 $1$，那么有转移 $\frac{f_{i-1,j}(\genfrac{}{}{0ex}{}{b_i}{k})}{2^{b_i}}\to f_{i,\lfloor \frac{j+k}{2}\rfloor }$。

考虑统计答案，设最大的那个数位数为 $i$，显然其他数不能在高于 $i$ 位出现 $1$，那么 $f_{i,0}$ 乘上 $>i$ 的位均为 $0$ 的概率即为答案，加起来即可。

QOJ5175 翻修道路

记 $f_{i,j,k}$ 表示从 $j$ 出发到达 $i$ 中的关键点修改 $k$ 次后最大距离的最小值，容易 $3^n{m}^3$ 转移，注意到合并两个状态是对两个数取 $max$，在第三维双指针即可，$O(2^n{m}^3+3^n{m}^2)$。

QOJ5098 第一代图灵机

假设没有修改，容易想到对于每个 $i$ 找到其作为右端点时最小左端点 $g_i$，有 $g_i=\underset{j=1}{\overset{i}{max}}pr{e}_j$，其中 $pr{e}_j$ 为最大的满足 $a_j=a_k,k<j$ 的 $k$。而前缀最大值这个东西无法简单维护，题解做法为线段树分治维护。

考虑直接用线段树做，求答案时需要满足所有数对应的左端点不小于询问的 $L$，因此考虑线段树上快速求出对于一个节点 $[l,r]$ 仅考虑 $pr{e}_{l\sim r}$ 和任意 $lim$ 限制时的答案。考虑对于一个节点 $[l,r]$ 维护仅考虑 $pr{e}_{l\sim r}$ 限制时 $[mid+1,r]$ 的答案（记为 $s_{l,r}$），假设这个值已经求出来了，考虑处理查询，有：

• 当 $\underset{i=l}{\overset{mid}{max}}pr{e}_i\ge lim$ 时，显然去掉 $lim$ 后右侧的数的限制不会变小，那么右侧答案即为 $s_{l,r}$，递归左侧后取 $max$ 即可。
• 当 $\underset{i=l}{\overset{mid}{max}}pr{e}_i<lim$ 时，显然左侧所有数的最紧限制均为 $lim$，左侧答案为 $\sum _{i=lim}^{mid}{a}_i$，递归右侧后取 $max$ 即可。

发现所有操作都是单侧递归的，复杂度为 ${\log }^2$。考虑求 $s_{l,r}$，不难发现 $s_{l,r}$ 即为查询右子树 $lim=\underset{i=l}{\overset{mid}{max}}pr{e}_i$ 的答案。

QOJ8670 独立

考虑求最大独立集的经典 dp：设 $d{p}_{x,0/1}$ 表示 $x$ 是否选中的答案。感性理解一下 $max(d{p}_{x,0},d{p}_{x,1})-d{p}_{x,0}$ 即为 $x$ 的贡献，大概就是包含 $x$ 的答案减去去掉 $x$ 的答案，多算的在后面一定会抵消，设 $f_{x,i}$ 表示 $max(d{p}_{x,0},d{p}_{x,1})-d{p}_{x,0}=i$ 的方案数，答案即为 $f_{x,i}\times i$ 再乘上外面的方案 $m^{n-siz{e}_x}$。

由于 $i$ 是值域范围的，考虑拉插，不难证明 $f_{x,i}(i\ne 0)$ 是关于 $i$ 的 $siz{e}_x$ 次多项式。考虑转移，相当于是 $\sum _u{f}_{u,p_u}\to f_{x,max(1-\sum _u{p}_u,0)}$，可以减法卷积得到任意 $m-siz{e}_x+1\sim m$ 后点值平移到 $1\sim siz{e}_x$。注意到式子中的 $max$，也就是 $<0$ 的全部会贡献到 $0$，可以一次拉插得到 $1\sim m$ 的答案后用总数减去即可。复杂度 $O(n^2\log n)$。