C. Canvas Painting
考虑一个子区间 $[l,r]$ 内部，如果有 $\ge r-l$ 个操作，那么该子区间中至多 $r-l$ 个操作是有用的，剩下操作是没用的。我们可以按长度从小到大考虑所有区间，如果一个区间中有 $>r-l$ 个操作，就不断随意删除操作直到剩下 $r-l$ 个。
事实上我们可以得到一个结论：如果每次选择的 $u,v$ 一定是相邻的，则仍能达到最优解。
假设加上这条限制，问题转化为：有一条链，每个操作 $[l,r]$ 可以匹配链上一个区间的边，求最大匹配。
转化完后就变成了经典的贪心匹配问题：将区间按 $r$ 排序，每次取 $[l,r]$ 中最左的没被匹配的点。时间复杂度 $O(m \log m)$。
D. Min-Max Tree
原问题可以转化为，把树剖成一堆链，每条链的权值为一端权值+，一端权值-，求总和的最大值。
从下到上 dp 即可。
E. tetrart
Clearly, the two necessary conditions for a solution are:
- No full rows.
- Empty rows must not have non-empty rows above them.
In fact, combining the two conditions will yield a sufficient criterion. Below, we provide a construction algorithm.
A natural approach is to build row by row, and ensure that no tetromino will fall below the current row (which destroys our previous construction). To simplify, we can build a platform, treating the area beneath it as void. First, place an inverted T, then extend outward with S and Z pieces, as the figures shown below:
brute force
Because dealing with "holes" (empty grids with blocks above them) is troublesome, we enforce a no-hole rule.(Grids below the platform don't count, as they are considered 'void')
Define the state as an array $a$ of length $w$, where $a_i$ represents the number of blocks in column $i$. Then, perform a search.
Testing shows that it suffices to search only the states satisfying $\max(a)\le 10,\max(a)-\min(a)\le 5$
Can also be constructed manually
final algorithm
For larger $w$, we divide the columns into groups of size $\ge 2$ and perform a similar procedure for each group separately.
In order to align the groups, we first enumerate the number of cleared rows ($l$), then we will know how many blocks have to be placed in each group, denoted by $c_1,\cdots,c_m$. Since $4\mid\sum c_i$ must hold, $l,c_i\bmod 4$ are uniquely determined.
Our next goal is to make $4|c_i$, so it will be possible that each tetromino belongs to exactly one group. If $4\nmid \sum_{i=1}^jc_i$, we can always place a tetromino spanning the groups $j$ and $j+1$ to fix that. For instance, std places a J,O or L (same direction as the letter).
Now that $4|c_i,\forall i$, we can put off the construction of the $1$st group to the very end, so the rightmost column will remain empty while we build groups $2\sim m$, and no line clear can occur during this process. When we finally start to build group $m$, since all columns that don't belong to this group are full, it is the same as $w=c_1,m=1$.
Because groups $1$ and $m$ are special (there is a hole in the underlying platform, and we need to consider line clear for group $1$), make sure that $c_1\ge 4,c_m\ge 3$.
Remember to memorize the search.
Overall time complexity: $O(X\times 7\times 4^2\log X+\sum wh\log X)$, where $X$ is the total number of states, $\approx 15000$(for $w=5$) or less.
Upper bound of moves: at most $h\times(10+1)w$ blocks will be cleared, so $k\le\dfrac{11hw+hw}{4}=3hw$
G. Sorting
It can sort if and only if for all $1 \leq i < n$, there exists $(i, i+1)$.
H. Walk
一条路径可以由 $N$ 个整数 $0\le h_0\le h_1\le\cdots\le h_{N-1}\le M$ 唯一确定，其中 $h_i$ 表示路径上所有横坐标是 $i$ 的点中，纵坐标最大是 $h_i$。
对于一个左下角是 $(x_1-0.5,y_1-0.5)$，右上角是 $(x_2+0.5,y_2+0.5)$ 的矩形：
- 路径同时穿过左右边界 $\Leftrightarrow h_{x_1-1}\ge y_1\wedge h_{x_2}\le y_2$
- 路径同时穿过上下边界 $\Leftrightarrow h_{x_1-1}\le y_1-1\wedge h_{x_2}\ge y_2+1$
用最小割模型来描述这种限制。从源点 $s$ 向汇点 $t$ 连 $N$ 条长度为 $M+1$ 的链，每条边的容量都是一个充分大的值 $W$，这样能保证每条链上恰好割掉一条边。
记 $(i,j)$ 为第 $i+1$ 条链上的第 $j+1$ 个点，即这 $N$ 条链分别是：
- $(0,0)\to(0,1)\to\cdots\to (0,M+1)$
- $(1,0)\to(1,1)\to\cdots\to (1,M+1)$
- $\quad\cdots$
- $(N-1,0)\to(N-1,1)\to\cdots\to(N-1,M+1)$
如果割掉了 $(i,j)\to(i,j+1)$ 就表示 $h_i=j$。
为了保证 $h_i\le h_{i+1}$，对于每对 $(i,j)$，从 $(i,j)$ 向 $(i+1,j)$ 连容量为 $+\infty$ 的边。
对于第 $i$ 个矩形，从 $(x_{i,1}-1,y_{i,1})$ 向 $(x_{i,2},y_{i,2}+1)$ 连容量为 $a_i$ 的边，从 $(x_{i,2},y_{i,2}+1)$ 向 $(x_{i,1}-1,y_{i,1})$ 连容量为 $b_i$ 的边。可能有一些边界情况要特判。
这样答案就是最小割减去 $N\times W$。
K. Counting
Fix $k$ and denote $A(i,j,k)$ by $f_{i,j}$. Let $F$ be $\sum f_{i,j}x^iy^j$, then $$ F=x\left(\frac{1}{1-F}+(y-1)F^k\right) $$ Let $G=\dfrac{x}{\frac{1}{1-x}+(y-1)x^k}$ then we have $F\circ G=x$. Using Lagrange Inversion on $F$, we have $$ \begin{aligned} \left[x^n\right]F&=\left[x^{n-1}\right]\frac{1}{n}\left(\frac{x}{G}\right)^n\\ &=[x^{n-1}]\frac{1}{n}\left((1-x)^{-1}+(y-1)x^k\right)^n\\ &=\sum_i\frac{1}{n}\binom{n}{i}(y-1)^i\left[x^{n-1}\right]x^{ki}(1-x)^{-(n-i)}\\ &=\sum_i\frac{1}{n}\binom{n}{i}\binom{(n-ki-1)+(n-i-1)}{n-i-1}(y-1)^i \end{aligned} $$ Note that $i$ is not greater than $\frac{n}{k}$, so the degree of $\left[x^n\right]F$ is bounded by $\frac{n}{k}$. Therefore, we can calculate $\left[x^n\right]F$ using NTT in $\mathcal O\left(\frac{n}{k}\log n\right)$ time.
Calculate the answers for every $k$, and we can preprocess all the answers in $\sum\limits_{i=1}^n\mathcal O\left(\frac{n}{i}\log n\right)=\mathcal O\left(n\log^2 n\right)$ time and answer each query in $\mathcal O(1)$ time.
L. cover
要最大化 $\sum [a_i \ne a_{i+1}]$。
初始序列可以看作是 $T=0$ 时刻有 $n$ 个长度为 $1$ 的区间操作。
$a_i \ne a_{i+1}$ 可能有两种方式产生，$a_i$ 比 $a_{i+1}$ 先操作或后操作。
由题目中的条件，后操作的区间不会严格被先操作的区间包含。假设 $a_i$ 是先操作的，$a_{i+1}$ 是后操作的，那么在 $i+1$ 之后就永远不可能有 $a_i$ 这个操作覆盖的元素了；反过来同理。
由此可以写出一个 $n^2$ DP：从左到右扫描序列，设 $f_{i,j}$ 表示第 $i$ 个元素，被第 $j$ 个操作覆盖了，前面的 $\max \sum [a_i \ne a_{i+1}]$ 值。转移讨论一下两种情况。
这个转移可以线段树优化 DP，大致要优化的过程是：
- 每个位置有一个 (dp 值，颜色) = $(val,c)$，也有可能没有
- 单点修改
- 对于一个 $(val',c')$ 对某个前缀做转移 $val \to \max(val,val'+[c\ne c'])$
- 给出颜色 $c'$，对一个前缀的 $(val,c)$ 求最大的 $val+[c\ne c']$
可以线段树维护，每个节点维护 $c$ 不同的最大的 $3$ 个 $val$，tag 记录 $c$ 不同的最大的 $2$ 个 $val'$。
时间复杂度 $O(n\log n)$。
