因为要求所有的状态，所以暴力超时

那么想想能否计算贡献。

我们对于每一个xi,xi+1，他们对于每一个fi的状态都有不同的贡献，因此我们枚举情况后用差分数组维护贡献

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
const int N=5e6+10;
const ll inf=1e16;
const int mod=998244353;
int n,m;
int a[N];
ll tr[N];
void modify(int l,int r,int x){
    tr[l]+=x;
    tr[r+1]-=x;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i;
    for(i=1;i<=m;i++){
        cin>>a[i];
    }
    for(i=1;i<m;i++){
        int l=a[i],r=a[i+1];
        if(l==r)
            continue;
        if(l>r)
            swap(l,r);
        modify(1,l-1,r-l);
        modify(l,l,r-1);
        modify(l+1,r-1,r-l-1);
        modify(r,r,l);
        modify(r+1,n,r-l);
    }
    for(i=1;i<=n;i++){
        tr[i]+=tr[i-1];
        cout<<tr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

View Code