题解 CF1234E 【Special Permutations】

2019-10-28 10:02:56


首先把 $pos(p_k(n),x)$ 写成一个比较好看的形式 $$ pos(p_k(n),x)=\begin{cases}x+1,&x<k\\1,&x=k\\x,&x>k\end{cases} $$ 考虑 $x_i$ 和 $x_{i+1}$ 这两个数对所有 $f(p_k(n))$ 值的贡献。根据初中数学套路,我们需要分类讨论:

  • 若 $x_i=x_{i+1}$ ,此时贡献全部为 $0$ 。
  • 若 $x_i\neq x_{i+1}$ ,我们令 $a=\min\left\{x_i,x_{i+1}\right\},b=\max\left\{x_i,x_{i+1}\right\}$ ,并分 $5$ 种情况讨论:
    • 若 $1\leq k<a$ ,此时 $|pos(p_k(n),x_i)-pos(p_k(n),x_{i+1})|=b-a$ ;
    • 若 $k=a$ ,此时 $|pos(p_k(n),x_i)-pos(p_k(n),x_{i+1})|=b-1$ ;
    • 若 $a<k<b$ ,此时 $|pos(p_k(n),x_i)-pos(p_k(n),x_{i+1})|=b-a-1$ ;
    • 若 $k=b$ ,此时 $|pos(p_k(n),x_i)-pos(p_k(n),x_{i+1})|=a$ ;
    • 若 $b<k\leq n$ ,此时 $|pos(p_k(n),x_i)-pos(p_k(n),x_{i+1})|=b-a$ 。

以上内容的证明都是初中数学知识,所以略去

于是用一个线段树/树状数组/差分维护所有 $f(p_k(n))$ 就好了。

代码