CodeForces1234E - Special Permutations 题解

一开始做麻烦了，关键是写麻烦了还没过，好气哦。

这题应该有很多不同的思路。我的想法是计算给出的数组中每一对相邻的数在之后的排列（Permutation）中距离的变化，然后只要以第一个排列的答案为基准，加上之后排列的距离变化就是后面排列的答案了。

那么距离是如何变化的呢，我们设一对相邻的数中比较小的数是 $l$ ，比较大的数是 $r$ ，那么他们在第一个排列中的位置就是这样的： $1,2,\ldots,l,\dots,r,\ldots,n-1,n$ 在第一个一直到第 $l-1$ 个排列中， $l$ 和 $r$ 的位置都没有发生变化，自然距离也不变。但在第 $l$ 个排列中， $l$ 成了第一个数： $l,1,2,\ldots,l-1,l+1,\dots,r,\ldots,n-1,n$

$l$ 与 $r$ 的距离增加了 $l-1$ 。

在第 $l+1$ 到 $r-1$ 个排列中， $l$ 与 $r$ 中的某一个数会在最前面，所以 $l$ 与 $r$ 的距离比最开始少 1。

在第 $r$ 个排列中，r 跑到了最前面： $r,1,2,\ldots,l-1,l,l+1,\dots,r-1,r+1,\ldots,n-1,n$ 注意此时 l 的位置依然是 $l+1$ ，所以距离的变化是 $(l+1-1)-(r-l)=2\cdot l-r$

如果我们用一个数组 a 来保存所有排列中答案的变化，那么对于每一对 $(l,r)$ ,我们应该做如下三个操作：

$a_l := a_l+l-1$
$a_i:= a_i-1,i=l+1,\ldots,r-1$
$a_r:= a_r +2\cdot l-r$

由于其中涉及到区间修改，所以我们可以用差分的思想来实现，并且由于只会查询一次，所以用最简单的数组就可以了，具体实现见代码：

#include <iostream>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define endl '\n'
using namespace std;
 
typedef long long ll;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
 
const int N=2e5+5;
ll sum[N];
int n,m;
void rgadd(int l,int r,int x){
    sum[l]+=x;
    sum[r+1]-=x;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
    cin>>n>>m;
    int x,last;
    cin>>last;
    ll ans=0;
    forn(i,m-1){
        cin>>x;
        int mn=min(x,last),mx=max(x,last);
        ans+=mx-mn;
        last=x;
        if(mx==mn) continue;
        rgadd(mn,mn,mn-1);
        rgadd(mx,mx,(mn-mx+mn));
        if(mx-mn>1)
        rgadd(mn+1,mx-1,-1);
    }
    for1(i,n){
        ans+=sum[i];
        cout<<an<<' ';
    }
  return 0;
}