【AtCoder Regular Contest 077 E】guruguru | Mrsrz's blog

差分。

题目大意：

给定一个环和一个数列 $a_1,a_2,a_3,\ldots,a_n$。你要从 $a_1$ 开始，顺时针行走，依次到达 $a_2,a_3,\ldots,a_n$。走一个单位花费 $1$ 的代价。

你可以确定一个位置为关键点，然后不管在什么地方，都可以花费 $1$ 的代价走到关键点处。

问总代价最小是多少。

题解：

我们考虑 $x$ 到 $y$ 的路径上，在 $x+2,x+3,x+4,\cdots$ 位置上放关键点并跳过去，会节约 $1,2,3,\cdots$ 步。

一个点能够节约的总步数，就是所有包含这个点的路径中，直接跳到这个点时能节约的步数。

我们考虑计算出每个点能节约的步数。对于一条路径，它会给一个区间加上一个等差数列。我们要在最后的时候查询所有值。所以只需要用二阶差分维护就好了。

至于环上的差分，我们可以倍长之后断环为链，然后在链上差分即可。

时间复杂度 $O(n+m)$。

Code：

#include<cstdio>
int n,m,d[114514];
long long ans,A[233333];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    scanf("%d",d+i);
    for(int i=1;i<n;++i){
        int l=d[i],r=d[i+1];
        if(l>r)r+=m;
        ans+=r-l;
        ++A[l+2],--A[r+1];
        A[r+1]-=r-l-1,A[r+2]+=r-l-1;
    }
    for(int i=1;i<=m*2;++i)A[i]+=A[i-1];
    for(int i=1;i<=m*2;++i)A[i]+=A[i-1];
    for(int i=1;i<=m;++i)A[i]+=A[i+m];
    long long mx=0;
    for(int i=1;i<=m;++i)if(mx<A[i])mx=A[i];
    printf("%lld\n",ans-mx);
    return 0;
}