【算法】浅谈一类转移带有数据结构操作特征的 DP 的优化 -永无岛

前言

有一类 DP 的转移是带有数据结构特征的，针对这一点，我们可以使用合适的数据结构来优化转移。
可能这么干说着不好理解，下面会给出两道题目来详细说明。

例子

1.【arc073f】Many Moves

题目大意：
你有两个整数 $a$ 和 $b$ 。
现在 $n$ 个操作，依次执行，每次给你 $xi$ ，你选择一个整数 $y$ 变成 $xi$ ，代价为 $|xi-y|$ 。
求做完所有操作的最小代价。
$n \leq 1e5，xi \leq 1e9$

先写出 DP 状态，然后来一步一步优化它。
令 $f[i][j][k]$表示，当前到了第 $i$ 步，一个整数为 $x_j$，另一个整数为 $x_k$的最小代价。
然后你发现当完成第 $i$ 步时，一定有一个数是 $x_i$，那么，我们可以把状态优化一下：
令 $f[i][j]$表示，当前到了第 $i$ 步，一个整数为 $x_i$，另一个整数为 $x_j$的最小代价。
把转移方程写出来：
$$
f[i+1][j]=f[i][j]+abs(x_{i+1}-x_{i}) \quad (j<i)\\
f[i+1][i]=min_{j<i}(f[i][j]+abs(x_{i+1}-x_{j}))
$$
在 i 相同时，第一个转移就是区间加，而第二个转移就是全局最小值之后单点赋值，这显然可以用线段树操作，复杂度 $\Theta (nlog_{2}n)$。

2.「HB 省队互测 2019 Round1 Day1」轮回

题目链接
其实这题最难想的是 $DP$ 的状态吧。
考虑，最后的结果一定是，有些动了，有一些没有动。而每一次的移动是任意插入的，那么，在排好 $1$ 到 $i-1$ 之后，如果我们知道最大的没有动的数，是不是说 i 的移动方向就确定了 (就是移到最大的没有动的数的后面)？而这么设计状态是没有后效性的，于是有了这样一个想法：
令 $f[i][j]$表示将序列中的元素 $[1,i]$排好序，且最大的没有被移动的数是 $j$ 的最小时间。
转移：
$$
if(pos_{j}<pos_{i}) \quad f[i][j]=f[i-1][j]+b\\
if(pos_{j}>pos_{i}) \quad f[i][j]=f[i-1][j]+a\\
if(pos_{j}<pos_{i}) \quad f[i][i]=min(f[i-1][j])
$$
这里有一个技巧，因为转移的时候讨论的是 pos 的大小关系，所以为了方便区间操作，我们在实际使用线段树时的下标 j 实际上表示的是 pos 为 j 的值，然后每次转移就是前缀最小值，单点插入，然后前缀加，后缀加。
好像有点难理解，正好这道题是我为数不多的认真写了的题目 (平常都是口胡)，放一波代码。(请原谅本人丑陋的码风).
虽然写的丑，但由于复杂度是 $O(nlogn)$, 比神仙学长 $huyufeifei$ 的 $O(n^2) std$快了将近 $30$ 倍，目前是 $GUOJ$ 本题 $rank1$（欢迎各位来踩我大常数 $O(nlogn)$代码）

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define inf 10000000000000
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
ll A,B;
#define ls(x) x<<1
#define rs(x) x<<1|1
void scan() {
    cin>>n>>A>>B;
    for(int i=1; i<=n; i++) {
        int x;
        scanf("%d",&x);
        a[x]=i+1;
    }
}
inline void push_up(ll p) {
    ans[p]=min(ans[ls(p)],ans[rs(p)]);
}
void build(ll p,ll l,ll r) {
    if(l==r) {
        ans[p]=inf;
        tag[p]=0;
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
    return;
}
inline void f(ll p,ll l,ll r,ll k) {
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k;
}
inline void push_down(ll p,ll l,ll r) {
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k) {
    if(nl<=l&&r<=nr) {
        ans[p]+=k;
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p) {
    ll res=inf;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res=min(query(q_x,q_y,l,mid,ls(p)),res);
    if(q_y>mid) res=min(res,query(q_x,q_y,mid+1,r,rs(p)));
    return res;
}
void opc(ll cp,ll l,ll r,ll p,ll zhi) {
    if(l==r&&cp==l) {
        ans[p]=zhi;
        return;
    }
    ll res=0;
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(cp<=mid) opc(cp,l,mid,ls(p),zhi);
    if(cp>mid) opc(cp,mid+1,r,rs(p),zhi);
    push_up(p);
    return;
}
int main() {
    ll a1,b,c,d,e,f;
    scan();
    build(1,1,n+1);
    opc(1,1,n+1,1,0);
    opc(a[1],1,n+1,1,0);
    update(1,a[1]-1,1,n+1,1,B);
    if(a[1]!=n+1)
        update(a[1]+1,n+1,1,n+1,1,A);
//  for(int j=1; j<=n+1; j++) {
//          cout<<query(j,j,1,n+1,1)<<" ";
//      }
//      cout<<endl;
    for(int i=2; i<=n; i++) {
        ll anss=query(1,a[i]-1,1,n+1,1);
        opc(a[i],1,n+1,1,anss);
        update(1,a[i]-1,1,n+1,1,B);
        if(a[i]!=n+1)
            update(a[i]+1,n+1,1,n+1,1,A);
//      for(int j=1; j<=n+1; j++) 
//          query(j,j,1,n+1,1);
    }
    cout<<query(1,n+1,1,n+1,1);
    return 0;
}

附：思考题 (我不会)

现在你有两个楼梯。有 $n$个人排成一条队，每个人有一个通过楼梯的时间 $t_{i}$。然后你每次可以让一个人从其中一个楼梯上楼 (按排队的顺序)。因为楼梯过窄，后面的人不能超越前面的人，所以后面的人到达的时间一定大于等于前面的人的最慢到达时间 (前面所有的人到达之后他才能到达)。定义一个人上楼的不爽值是他最终上楼所花的实际时间-$t_i$。请你最小化所有人的不爽值之和。
$n \leq 1e5，t \leq 1e9$。

完结撒花！