arc206 总结
这次前面切得比较快，然而 D 题漏了情况卡到最后也没过。E 题也属于中等难度的题。
A
枚举题目中的 \(L\)，一个连续段只能有一个 \(L\)，对答案的贡献为其后面不等于 \(a_L\) 的个数。
复杂度 \(O(n)\)。
B
因为颜色的值域为 \(n\)，所以我们每次可以新赋一个没出现过的颜色，所以不同颜色之间不会影响。分割出每个颜色构成的子序列，那么最多有「最长上升子序列的长度」个位置不用改变颜色。
复杂度 \(O(n \log n)\)。
C
分析好的序列的条件，对于 \(r=l+1\)，发现要么 \(a_i={i+1}\) 要么 \(a_{i+1}={i}\)。进一步发现，好的序列形如存在一个点 \(M\)，使得左侧点都有 \(a_i={i+1}\)，右侧点都有 \(a_i={i-1}\)，而 \(a_M\) 可以随便连。
那么枚举第一个满足 \(a_i\ne i+1\) 的位置统计答案可以不重不漏。
复杂度 \(O(n)\)。
D
对于 \(K\ge2\) 可以构造 \(n-K+1,\dots ,n,n-K,\dots ,1\)。
对于 \(K=1\) 发现，\(n=2,3,4\) 时无解，对于 \(n\ge 5\) 可以构造 \(4,1,3,5,2,6,\dots,n\)。
对于 \(K=0\)，比较难发现的是 \(n\ge 8\) 时是有解的，可以构造 \(6,5,1,2,7,8,4,3,9,\dots,n\)。
复杂度 \(O(n)\)。
E
为了把 \((1,1),(1,n),(n,1),(n,n)\) 填上，则「右上」「左上」「右下」「左下」之间是必须选的。
则每个方向都至少选了 2 个。假设选了 \(u_1<u_2\)，其他同理，那么这 8 个点已经合法的条件为不存在 \(u_2+1<d_1\land r_2+1<l_1\) 且不存在 \(d_2+1<u_1\land l_2+1<r_1\)。
若不合法，我们只能再在上下或左右组成一队，发现此时一定合法。
则答案为「一组对边分别选三个，另一组对边分别选两个」或「每组对边分别都选两个，要求合法」。
对于后者，可以预处理前缀后缀 \(\min\)，分为 \(u_2+1=d_1\)，\(d_1\in [u_1,u_2]\)，\(u_2+1<d_1\land l_2+1<r_1\) 三种情况。复杂度 \(O(\sum n)\)。