【AtCoder Regular Contest 073 F】Many Moves | Mrsrz's blog

李超树优化 DP。

题目大意：

给定两枚硬币，初始在 $A$ 和 $B$ 位置。

给出 $n$ 和 $x_1,x_2,x_3,\ldots,x_n$，你要进行 $n$ 次对硬币的移动。第 $i$ 次你需要将至少一枚硬币移动到 $x_i$ 位置，另一枚随意。

一枚硬币从 $p$ 移动到 $q$ 的代价是 $|p-q|$。

问完成 $n$ 次移动的最小代价。

题解：

我们令 $dp_i$ 表示当前有一枚硬币在 $i$ 位置，另一枚硬币在目标位置的最小代价。

从上一种状态转移到当前状态有两种不同转移（其中一枚强制移动到目标位置，可以是上一轮在目标位置的硬币也可以是上一轮不固定的硬币）。

对于目标状态移动到目标状态的，我们只需要做一个全局加法即可。至于另一枚硬币，我们默认它在之前某次移动的时候就到了它之后要到的位置，所以可以不用管。

对于非目标状态移动到目标状态的，我们默认它在某一轮已经移动到这个位置了，所以直接查询上一轮 $dp_{x_i}$ 的值。至于另外一枚从原来的目标状态变成自由移动的硬币，它的转移是一个绝对值函数。由于我们的 DP 是取 $\min$，所以把绝对值函数分成两个一次函数。

全局加直接打标记，一次函数部分，我们用李超树维护最值即可。

时间复杂度 $O(n\log^2 n)$，常数小。

Code：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+7;
int n,q,A,B,X[N];
typedef long long LL;
struct node{
    LL L,det;
}d[N<<2];
void modify(int l,int r,int o,const int&L,const int&R,const LL&val,const int&delta){
    if(L<=l&&r<=R){
        LL yL=d[o].L,yR=yL+(r-l)*d[o].det;
        LL nL=val+(l-L)*delta,nR=nL+(r-l)*delta;
        if(nL>=yL&&nR>=yR)return;
        if(nL<=yL&&nR<=yR){d[o]=(node){nL,delta};return;}
    }
    const int mid=l+r>>1;
    if(L<=mid)modify(l,mid,o<<1,L,R,val,delta);
    if(mid<R)modify(mid+1,r,o<<1|1,L,R,val,delta);
}
LL TAG;
LL query(int l,int r,int o,const int&pos){
    if(l==r)return d[o].L;
    LL nans=d[o].L+(pos-l)*d[o].det;
    const int mid=l+r>>1;
    if(pos<=mid)return min(nans,query(l,mid,o<<1,pos));else
    return min(nans,query(mid+1,r,o<<1|1,pos));
}
int main(){
    scanf("%d%d%d%d",&n,&q,&A,&B);
    for(int i=1;i<=n*4;++i)d[i].L=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=q;++i)scanf("%d",X+i);
    modify(1,n,1,B,n,abs(A-X[1]),1);
    modify(1,n,1,1,B,abs(A-X[1])+B-1,-1);
    modify(1,n,1,A,n,abs(B-X[1]),1);
    modify(1,n,1,1,A,abs(B-X[1])+A-1,-1);
    for(int i=2;i<=q;++i){
        LL as=query(1,n,1,X[i]);
        modify(1,n,1,X[i-1],n,as-abs(X[i]-X[i-1]),1);
        modify(1,n,1,1,X[i-1],as+X[i-1]-1-abs(X[i]-X[i-1]),-1);
        TAG+=abs(X[i]-X[i-1]);
    }
    LL ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;++i)
    ans=min(ans,TAG+query(1,n,1,i));
    printf("%lld\n",ans);
    return 0;
}