题量这么大还没签到题，差评了。
A. ABC Legacy
我们可以求出三种子序列各划分出了多少个，设为 \(x,y,z\)，则 \(cnt_A=x+y\)，\(cnt_B=x+z\)，\(cnt_C=y+z\)，不难求出 \(x,y,z\)。从 \(B\) 出发考虑，它要作为 \(BC\) 出现 \(z\) 次，作为 \(AB\) 出现 \(x\) 次。显然将前 \(z\) 个 \(B\) 作为 \(BC\) 出现最优，此时 \(C\) 一定取某个 \(B\) 后面第一个没匹配的 \(C\)，这样做完以后只需要 check 一遍 \(AC\) 是否合法。
B. New Queries On Segment Deluxe
考虑没有可持久化怎么做。注意到 \(k\) 很小，尝试对列建立线段树然后维护所有行的信息，需要维护区间最小值，修改操作需要加法标记和赋值标记，下传标记的时候区间最小值并不是很好更改。对于行的每个子集，维护其和的最小值，这样区间最小值信息是好修改的，同时注意到子集信息也是可以相互推出的。时间复杂度 \(O(q\log n2^k)\)，最后加一个主席树即可。
C. Counting Phenomenal Arrays
一个直观感觉是，\(>1\) 的数不会很多，实际上确为如此。考虑对于所有 \(>1\) 的数求出 \(x=\prod-\sum\)，那么需要添加 \(x\) 个 \(1\) 使其合法。注意到数组里面的数是 \(O(n)\) 级别，更确切地可以分析到 \(\leq n\)，\(ab-a-b\geq 2(n+1)-2-(n+1)\geq n-1\)。感受到不断加入 \(>1\) 的数后 \(\prod-\sum\) 增长速度非常快，于是后面直接搜即可。
D. LIS Counting
问题的结构非常复杂，用双射来简化问题，题目中 \(NM\) 的形式提示映射到矩阵。下文 \(i\) 均指下标，\(p_i\) 指值。
令 \(inc_i\) 代表以 \(i\) 结尾的 LIS 长度，\(dec_i\) 代表以 \(i\) 结尾的 LDS 长度，可以说明，在同一个序列中 \((inc_i,dec_i)\) 互不相同。设 \(i<j\)，分析一下 \(p_i\) 和 \(p_j\) 的大小关系即可。
建立两个矩阵，\(A_{inc_i,dec_i}=i\)，\(B_{inc_i,dec_i}=p_i\)。考察矩阵的性质，可以发现 \(A\) 行列均递增，\(B\) 行减列增。同时对于一个合法的长为 \(nm\) 的序列，\(A\) 和 \(B\) 一定均被填满，同时形成双射。\(p\to(A,B)\) 是单射很好说明，\((A,B)\to p\) 是单射需要说明任何 \((A,B)\) 均能生成合法的 \(p\)，说明此点后恰好生成一个是显然的。对于一对 \((A,B)\) 生成一个序列 \(p\) 后，可以说明其必然合法。
对于 \(i:1\to nm\)，依次将 \(A\) 中值为 \(i\) 的位置染色，可以发现任意时刻染色必然为包含右上角的，轮廓不存在凹陷的连通块。新加入 \(i\) 时，考虑其 \(inc_i\) 实际上是从先前连通块中找到值小于其且 \(inc\) 最大的位置，\(inc\) 最大表现为最靠下，从 \(B\) 出发考虑，新染色点的上方显然是一个合法的位置，同时不存在其它更靠下的合法位置，因为 \(B\) 是行减列增的。\(dec\) 的分析同理。
我们要求的 \(f(pos,val)\) 即为在 \(AB\) 同一个位置上分别为 \(pos\) 和 \(val\) 的矩阵数量。对上面的染色过程 dp，维护轮廓线，可以统计出 \(g_0(i,j,pos)\) 代表 \(A_{i,j}=pos\) 的方案数，由于 \(AB\) 完全独立，各做一遍然后乘起来即可。对 \(B\) 的 dp 顺序需要从右上角开始。时间复杂度 \(O(\binom{n+m}nnm+(nm)^3)\)。
E. Flood Fill
建图。注意到有边的两个连通块在最后的矩阵中不可能同时被改变颜色，同时选择原图的一个独立集，钦定这些连通块改变颜色是一定可以做到的，图是二分图，所以问题等价于二分图最大独立集，网络流即可。
F. to Pay Respects
考虑什么时候让对手中毒最优，如果存在一个让对手中毒的时刻 \(i\)，同时对手存在一个回血的时刻 \(j\)，且 \(j\) 上没有中毒，\(i>j\)，那么将 \(i\) 上的中毒移到 \(j\) 一定更优，因为中毒本身就是越往前越优，唯一制约其的就是抵消回血这一效果。因此最后的中毒时间形如一段前缀加上若干回血的时间点，枚举最后一个中毒的时间即可。
G. Replace Sort
对 \(B\) 排序。考虑将 \(A\) 中的若干连续段替换成 \(B\) 的一个连续段，令 \(f_i\) 代表 \(i\) 处没有连续段的最小值，\(i-1\) 处没有连续段的情况可以直接转移。以下讨论 \(i-1\) 处有连续段的情况。
我们必然是将 \(A_{i-1}\) 替换成 \(B\) 中小于 \(A_i\) 的最大值，需要满足这个值 \(>A_{i-1}\)。显然这个值在此前不会被使用。同理，设连续段开头为 \(j+1\)，将 \(A_{i-1}\) 替换为 \(B_x\)，那么整个连续段就是将 \(A_{j+1\sim i-1}\) 替换为 \(B_{x-(i-j)+2\sim x}\)，写出转移条件：
第一个条件主要体现在下标上，考虑将其转化。设 \(c_i\) 为最小的 \(j\) 使得 \(A_i<B_j\)，若不存在则为 \(\infty\)，那么条件改写为：
这是唯一的条件，因为原先的第二个条件被此蕴含。线段树直接优化即可，时间复杂度 \(O(n\log n)\)。存在常数更小的做法，注意到 \((c_j-j,f_j)\) 带来了很多支配对，删掉不需要的支配对以后可以发现剩下的决策点一定是最大的 \(c_j-j\) 带来，set 维护即可。
H. Werewolves
枚举颜色 \(i\)，考虑组合意义。将 \(c_j=i\) 的点权设为 \(1\)，否则设为 \(-1\)，等价于查询树上权值 \(>0\) 的连通块数量，根据树上背包经典结论，做这个的复杂度是 \(O(nk)\)，其中 \(k\) 是颜色 \(i\) 的出现次数，总复杂度 \(O(n^2)\)。
I. Colourful Permutation Sorting
存在最优方案使得所有操作一在操作二之前。考虑最终序列的形态，如果一些数所处的颜色改变了，那么交换这些数是必然需要的，先将这些交换做完，此后的交换只会发生在同种颜色间，每种颜色是独立的，那一种颜色先做操作二在做操作一显然不优。同时每种颜色只会做一次操作二。
不存在操作二时的经典结论是答案为 \(n-cyc\)，\(cyc\) 为置换环数量。枚举哪些颜色做操作二，每个颜色的所有点可以缩成一个大点，我们想最大化图上的环数，每条边只能位于一个环中。缩掉二度点，则剩下最多 \(k\) 个点，同时每个点入度等于出度。自环直接删去，二元环也直接删去。三元环不能直接删去的原因是，假设最终答案中三条边在不同的环上，那么将三条边放在同一个环中，剩下三个缺一条边的环可能只合成一个环，环数减小。
实际上，如果我们能按顺序删去自环、二元环、三元环、四元环、五元环，那么是对的。上面的分析需要三条边在最终答案中处于不同的环，这些环至少是三元环（二元环和自环已经被删去了），那么顶点数至少是 \(6\)，由于最多 \(5\) 个点，所以必然有重复的顶点，可以多拆出一个简单环。四元环同理但复杂一点，四条边在不同环中的情况和上面一样，四条边在三个环中，顶点数至少为 \(12\)，肯定可以多拆出一个简单环。
还有一些别的做法。当不超过 \(4\) 个点的时候，一定可以找到一个点满足出点只有一个，合并即可。五个点的时候可以构造出如下反例（题解说每个点的入点数和出点数都为 \(2\)，下面这张图显然是不符合的，我也不知道是不是 typo）：
但是一定有出点数为 \(2\) 的点，暴力枚举配对方式可以缩掉这个点。其实我也不知道这句话是什么意思，看不懂。
上述所有过程都要不断删去自环和二元环。