写个题解。以后看一次后悔一次。

Tender Carpenter

不难发现，每个数单独一段一定是可行的。因为能够组成等边三角形。那么问题就变成了，能否分出一段长度不小于 \(2\) 的区间，使得其合法。显然的，\([l,r]\) 的可行性不大于 \([l+1,r]\) 的可行性。那么枚举 \(l=i,r=i+1\) 判断是否合法即可。

Outstanding Impressionist

当一个区间 \(i\) 不是特殊的，当且仅当对于每个 \(l_i \le j \le r_i\)，存在 \(l_k=r_k=j\)。然后直接判断即可。

Bewitching Stargazer

不难发现答案可以直接计算其中一半，然后递归下去。复杂度 \(O(\log n)\) 的。

Refined Product Optimality

答案显然是排序之后的 \(\prod \min(a_i,b_i)\)。那么对于修改 \(a_i\)，如果 \(a_i+1\) 后仍不大于第一个比 \(a_i\) 大的数，那么 \(a_i\) 对应的 \(b_i\) 不变。如果大于，相当于是将 \(a_j=a_i\) 的整体左移一位，然后空出来的一位匹配 \(a_i\)。修改 \(b_i\) 同理。这样不难发现每次修改只会最多影响到 \(2\) 组映射，直接维护即可。

Resourceful Caterpillar Sequence

注意到情况只有 \(2\) 种。第一种是 \(q\) 一开始就在叶子节点；第二种是对于 \(p\) 移动一步之后的所有情况，\(p\) 距离最近的叶子节点距离都是 \(1\)。情况 \(1\) 证明显然，情况 \(2\) 若存在移动一步之后 \(p\) 无法直接移动到叶子节点，那么他们就可以无限拉扯，直到平局。

计算情况 \(1\) 简单。对于情况 \(2\)，可以考虑枚举 \(q\) 随着 \(p\) 移动一步之后的位置 \(x\)，那么 \(x\) 需要有一个出边连向叶子节点。同时，当 \(d_x \ge 3\) 时，我们就可以把 \(q\) 放在其中一个子树里，\(p\) 放在另一个子树里。有个显然的事情，\(p\) 只能往深度大的点走，所以这样 \(q\) 一定能走到 \(x\)。那么 \(p\) 应该为所有距离最近叶子节点长度不小于 \(2\) 的点。而对于每个 \(q\)，都能对应到所有的 \(p\)。也就是说，对于一个 \(x\)，其贡献应该是 \(c_x \times cnt\)。其中 \(c_x\) 为 \(x\) 出边不为叶子节点的数量，\(cnt\) 为 \(p\) 的数量。这个可以直接预处理 \(cnt\)，暴力枚举 \(x\)。

Earnest Matrix Complement

首先有性质：每一行的 \(-1\) 变成的数一定相同。证明简单。

定义状态函数 \(f_{i,j}\) 表示前 \(i\) 行，第 \(i\) 行的 \(-1\) 选 \(j\) 的数量。记 \(c_i\) 为第 \(i\) 行 \(-1\) 的数量，\(d_{i,j}\) 为第 \(i\) 行 \(j\) 的数量。那么有转移方程：\(f_{i,j}=\max(f_{i-1,w}+c_{i-1}\times d_{i,w}+c_i\times d_{i-1,j},f_{i-1,j}+c_i \times c_{i-1}+c_{i-1}\times d_{i,j}+c_i \times d_{i-1,j})\)。然后再加上一个定值，即 \(\sum\limits_{j=1}^{k}\sum\limits_{i=1}^{n-1}d_{i,j}\times d_{i+1,j}\)。如果我们改变一下转移形式，可以得到：\(f_{i,j}=\max(mx,f_{i-1,j}+c_{i-1}\times c_{i})+c_{i} \times (d_{i-1,j}+d_{i+1,j})\)。其中 \(mx=\max\limits_{j=1}^{k} f_{i-1,j}\)。不难发现，\(d_{i-1,j}+d_{i+1,j}\ge 1\) 的 \(j\) 数量为 \(O(m)\) 个。那么去掉后面的部分后就是一个整体加 \(x\)，整体取 \(\max\)。后面部分暴力更新单次是 \(O(m)\) 次的。直接线段树维护的时间复杂度 \(O(nm\log nm)\)。