P10033 「Cfz Round 3」Sum of Permutation

原题链接

基础赛唯一写了的题，因为我喜欢构造！

事实上的确有点麻烦了，应该会有更好的做法。但是自我感觉这个思维很连贯，因为这就是我做题时思路的写照。

记 \(p_{pos1}=1,p_{posn}=n\)。

首先可以构造 \(a_i\gets p_i+1\) 这样一定满足第二个限制，但是当 \(p_i = n\) 时不满足第一个限制。

钦定 \(pos1<posn\)，否则将整个序列翻转即可使 \(pos1<posn\)。

先假设 \(posn\not = n\)（由于钦定了 \(pos1<posn\) 所以 \(posn\not = 1\)）。

于是考虑对于 \(j < posn,a_j\gets p_j+1\)，对于 \(j > posn,a_j\gets p_j-1\)，\(a_{posn}=n-{posn}\)。

证明一下为什么正确。当区间 \([l,r]\) 不包含 \(posn\) 即完全位于左边或者右边时，其相当于一开始那个东西，是肯定正确的。当区间 \([l,r]\) 包含 \(posn\)，发现 \(\forall i<posn,\sum\limits_{j=i}^{posn-1} (a_j-p_j)\in [1,posn-1]\)，在加上 \(a_{posn}-p_{posn}\) 之后范围变成 \([1-posn,-1]\)，再往后加也一定是负数，不会为 \(0\) 所以不会相等。

再说 \(posn = n\)，你会发现这种时候直接用上面那种 \(p_n=0\) 就寄了。但是这种特例很好处理，只需要 \(j<n,a_j\gets n,a_n=\begin{cases} n-1 & p_{n-1}\not = n-1 \\ n-2 & p_{n-1} = n-1 \end{cases}\) 即可。

然后你发现 \(n\leq 2\) 这个东西又寄了，然后你发现 \(n\leq 2\) 无解。