Codeforces

Luogu

分析

首先把 $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))$ 就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,x[N];

ll c[N];
inline void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
inline void modify(int l,int r,int w) { add(l,w),add(r+1,-w); }
inline ll sum(int x) { ll s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) x[i]=read();
    for (re int i=1;i<m;++i) {
        if (x[i]==x[i+1]) continue;
        int a=min(x[i],x[i+1]),b=max(x[i],x[i+1]);
        modify(1,a-1,b-a);
        modify(a,a,b-1);
        modify(a+1,b-1,b-a-1);
        modify(b,b,a);
        modify(b+1,n,b-a);
    }
    for (re int i=1;i<=n;++i) printf("%lld ",sum(i)); puts("");
    return 0;
}
最后修改:2019 年 10 月 28 日 09 : 41 AM