cf1234 E. Special Permutations

题意：

有一个 /(1/sim n/) 的从小到大的排列，即 /(1,2,/cdots ,n/)，记为 /(P_1/)

定义 /(P_i/) 为：在 /(P_1/) 中把数字 /(i/) 移到最前面，其他数字的相对位置不变得到的新排列

定义 /(p_x(P_i)/) 为数字 /(x/) 在排列 /(P_i/) 中的位置

给定数组 /(a[]/)，定义函数 /(f_i/) 为 /(/Sigma |p_{a_k}(P_i)-p_{a_k}(P_i)|/)

输出 /(f_1,f_2,/cdots ,f_n/)

思路：

法一：

考虑从 /(P_x/) 到 /(P_{x+1}/) 有什么变化，实际上只有 /(p_x/) 从 /(1/) 变成 /(x+1/)，同时 /(p_{x+1}/) 从 /(x+1/) 变成 /(1/)，其他都不变。所以可以每次修改被影响的位置，求出所有 /(f/)

实现起来感觉很丑，不写了。下面的方法比较优雅

法二：差分

把要求的 /(f[]/) 写成差分数组，初始所有 /(f_i=0/)

考虑一对在 /(a[]/) 中相邻的数 /(x=a_k,y=a_{k+1}/)，不妨设 /(x<y/)。那么 /(x,y/) 对某个 /(f_i/) 的贡献是多少呢？

1. 若 /(i<x/)，则 /(p_x=x,p_y=y/)，对 /(f_i/) 的贡献就是 /(y-x/)，即 /(f_i+=y-x/)

2. 若 /(i=x/)，则 /(p_x=1,p_y=y/)，那么 /(f_i+=y-1/)

3. 若 /(x<i<y/)，则 /(p_x=x+1,p_y=y/)，那么 /(f_i+=y-x-1/)

4. 若 /(i=y/)，则 /(p_x=x+1,p_y=1/)，那么 /(f_i+=x/)

5. 若 /(i>y/)，则 /(p_x=x+1,p_y=y+1/)，那么 /(f_i+=y-x/)

也就是说，/(x,y/) 会让 /(f_x/) 加上 /(y-1/)，同时让 /(f_y/) 加上 /(x/)，让 /(f_{(x,y)}/) 加上 /(y-x-1/)，让 /(f_{[1,x)}/) 和 /(f_{(y,n]}/) 加上 /(y-x/)

用差分数组实现上述区间加操作，最后求一下前缀和得到原数组

const signed N = 2e5 + 3;
int n, m, a[N]; ll f[N];

void add(int l, int r, int val) {
    f[l] += val, f[r+1] -= val;
}

signed main() {
    iofast;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i];

    for(int i = 1; i < m; i++) {
        int x = a[i], y = a[i+1];
        if(x == y) continue;
        if(x > y) swap(x, y); //保证x<y
        add(1, x - 1, y - x);
        add(x, x, y - 1);
        add(x + 1, y - 1, y - x - 1);
        add(y, y, x);
        add(y + 1, n, y - x);
    }

    for(int i = 1; i <= n; i++) //前缀和
        cout << (f[i] += f[i-1]) << ' ';
}