ARC187
- 直接做没有思路？考虑换一个角度！不要被已经的思路局限！
- 全部类型的计数题拆一下贡献！
- 对于单次冒泡排序 \([1, i]\) 的前缀会在遍历到 \((i+1)\) 时确定。遍历到 \(i\) 时 \(i\) 位置上一定是前缀最大值，这也是一种刻画方法！
- 对于最小化极差类问题，考虑直接枚举某一个值然后另一个值枚举，省选联考卡牌也是如此。
A
死因：看到非递减序列，看到神秘交换，直接想到使用差分数组刻画，但是这样太难了，做不了，然后我就不会看 T2 去了（因为看上去更容易刻画）实际上是两个都搞炸了，破防离场。所以说如果这个行不通就应该及时换思路而不是对着它死磕。
进行一定观察，发现如果连续进行两次 \(i\) 操作会产生 \(A_i + k, A_{i+1}+k\) 的效果。这个没什么动机，就是单纯的观察，而且也不难，可能可以手玩得到。
然后我们就可以构造 \(1\sim (n - 1)\) 合法。考虑 \(A_n\) 的情况。
- \(A_n \ge A_{n - 1}\) 直接合法。
- \(A_n < A_{n - 1}, A_n + k \le A_{n - 1}\)，此时交换一次后可以不断对最后两个位置同时 \(+k\)。
- \(A_n < A_{n - 1}, A_n + k > A_{n - 1}\)，注意到此时给 \(A_{n - 1},A_{n - 2}\) 同时 \(+k\) 就变成第二种情况了。
B
最严重的问题出在观察到每个联通块一定是一个区间后没有想到按照 \((i, i+1)\) 这个缝隙来刻画和计算不在一个联通块的充要条件，这样的话实际上我们只要分析两个块即可。我一开始分析的充要条件是针对一个序列的整体计算的，导致前面到后面影响很大，不利于直接计数。
如果从一个二维平面的角度考虑，那么一个点能到的连边就是它左下角的所有点，此时不难想到一个联通块都在一个区间内的性质。现在考虑为什么 \([l, p], [p+1, r]\) 会到两个联通块去。这等价于 \(\forall i \in[l, p], a_i > \max\limits_{x\in[p+1, r]}a_x\)，也就是 \(\min\limits_{x\in [l, p]}a_x > \max\limits_{x\in[p+1, r]}a_x\)，然后直接 dp 即可。
这种拆贡献没有想到，必须严肃拷打。
C
这道题就更搞笑了，做了一万遍冒泡排序，但是仍然没弄清它怎么刻画。对于这道题实际上是直接刻画的，到了 \(i\) 这个位置上实际上是前缀最大值，同时可以确定 \((i - 1)\) 取值。显然的，用 \((i, j, S)\) 代表扫描到第 \(i\) 个位置，前缀最大值为 \(j\)，目前用了 \(S\) 内的数，可以刻画好一个盘面，直接转移即可。然后发现 \(S\) 太大了，但是注意到我们只关心 \(S\) 中小于 \(j\) 有多少空位，和大于 \(j\) 有多少空位，大于 \(j\) 全是空位，小于 \(j\) 只有 \(i\) 个位置有值，所以可以将这些 \(S\) 直接合并起来。
所以设 \(f[i, j]\) 为前 \(i\) 个数，前缀最大值为 \(j\) 的方案数，那么
-
\(Q_{i} = -1\)
- \(k > j\) 那么转移到 \(f[i + 1, k]\)。
- \(k = j\)，那么要搭配 \((j - i - r)f[i, j]\) 这个系数，其中 \(r\) 为 \(Q_{i+1}\sim Q_n\) 中不为 \(-1\) 且小于 \(j\) 的数量。注意若 \(Q_{i+1}< j\)，此时 \((i+1)\) 位置无法填 \(Q_{i+1}\)。
- \(k\ge j\)，同时 \(k\) 不等于除了 \(Q_{i+1}\) 以外所有出现过的 \(Q\)
-
\(Q_{i} \not= -1\)
- \(j = Q_{i}\)，那么 \((n - j - r)f[i, j]\) 转移到 \(f[i + 1, k]\)，\(k\) 条件同上，\(r\) 同上。
- \(j \not= Q_i\)，那么 \(f[i, j]\) 转移到 \(f[i+1, j]\)。
上面的有点问题，后来又推了，不管了我咕咕咕
ARC156
C
对于这种构造题，要记住 \(N\le 5000\) 不一定是这道题是个 \(O(N^2)\) 的树上 dp，也有可能是出题人的 checker 写不到太优秀，虽然这听起来挺搞笑的，但是我一开始的确是这样想的。
LCS 没有什么好的手法来刻画，那么我们应该从局部开始考虑。链和菊花图。链显然是倒序最后 LCS 为 \(1\)，因为两个序列一定会出现重复元素，所以 LCS 不可能更小。对于菊花图也同理。我们不难发现答案的下限实际上是 \(1\)，因为对于 \(x\) 我们总是可以找到 \(P_y = x\) 的 \(y\) 联系起 \(x, y\) 使得答案至少为 \(1\)。那么到了这里是不是可以大胆猜测可以构造答案为 \(1\) 的方案了呢？
考察 LCS 为 \(1\) 的序列的充要条件，只保留再两个序列中同时出现过的数，那么应该是严格的倒序。同时考虑在树上的一些内容，注意到树上只有两个端点都是叶子的路径才可能产生贡献。结合菊花图和链的情况，可以想到可以每次删除两个叶子 \(u, v\)，接着使 \(p_v = u, p_u = v\)。如果最后删除到它们的 LCA 处只剩下一个孤点，那么此时是完全倒序，否则完全删完的话 LCA 的值就不在之中了，那么也是倒序的。这样的构造是合法的。
总结一下，这道题应该首先从特殊情况出发（链，菊花图），然后考虑答案的可能下界。对于构造题，这些下界往往就是可以构造出来的。然后再考虑构造方法。考虑构造的时候，及时排除不优的可能，以此简化结构。
D
神了！