P17210 【模板】半在线决策单调性 题解

· · 题解

题目传送门：P17210 【模板】半在线决策单调性

前置知识：决策单调性

对于 DP 最优化转移，若 f_i 从 f_j 转移而来，则记 p_i=j 为 i 的最优决策点。

若对于 i<j 都有 p_i \leqslant p_j，则称 f 有决策单调性。

常见的一种决策单调性的充分条件是四边形不等式，可以用反证法证明。

四边形不等式：若对 a \leqslant b \leqslant c \leqslant d，总有 w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)（交叉小于包含），则称函数 w 满足四边形不等式。

:::info[证明] 不妨记 p_i 为 i 最大的一个最优决策点。

假设存在 a < b < c < d，满足 p_c=b,p_d=a，则有 w(a,d)>w(b,d) 且 w(a,c) \leqslant w(b,c)，即 w(a,c)-w(b,d) > 0 \geqslant w(a,c)-w(b,c)，与四边形不等式矛盾。 :::

此外，存在两种限制性质。

如果 w(j,i) 可以随地计算，则称其是支持随机访问的。

若 w 只支持移动访问，且需要动态计算，则有一种简化 LARSCH 算法可以在 O(n \log n) 时间内分治求解 f。

前置知识：简化 LARSCH 算法

当求解 [l,r] 的最终决策点及 DP 值时，假设我们已经知道了：

记 mid 为区间 [l,r] 的中点，则：

那么如何证明第一步遍历区间 [p_{l-1},p'_r]，时间复杂度还是分治的 O(n \log n) 呢？

若 w 支持随机访问，每一层的 [l,mid] 部分遍历的是 [p_l,p'_{mid}]，(mid,r] 部分遍历的是 [p_{mid},p'_r]，因为 p_{l-1} \leqslant p'_{mid} \leqslant p_{mid} \leqslant p'_r，所以每层每个决策点只会被访问一次。

当 w 只支持移动访问时，可以为第一步和第三步分别维护上一次查询的指针 (i,j) 及决策值，使用时像莫队一样暴力转移，总时间复杂度依旧是 O(n \log n)。

证明考虑左右指针的移动次数，每层可以视为跑一个来回。

:::info[证明] 对于 [p_{l-1},p'_r] 的左指针，已经证明；

对于 [p_{l-1},p'_r] 的右指针，每次分治由上一层的 mid 移动到本层 mid，距离为区间长度量级；

对于 [l,mid] 的左指针，移动距离为区间长度；

对于 [l,mid] 的右指针，每次分治可能由上一层的 r 移动到上一层的 mid，距离为区间长度量级。 :::

题目分析

状态 f_i 为划分 1 \sim i 得到的最小权值和，不难得到转移：f_i = \min\limits_{j<i}f_j+w(j,i)+b_i。此处我们重定义 w(l,r) 表示左开右闭区间 (l,r] 中，a_i=a_j 且 i<j 的下标对数量，这个东西需要移动计算，同时转移式里还有 f_j，因此也需要动态计算。

接着我们要证明其决策单调性。b_i 是常量就舍去，我们重定义的 w 显然是满足四边形不等式的（证明见下），作为四边形不等式的左端点，f_j 对两式的贡献相同，因此满足。

:::info[w 满足四边形不等式的证明] 我们试图证明对 a \leqslant b \leqslant c \leqslant d，总有 w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)。

分别考虑每个元素 x，记其在区间 (a,b],(b,c],(c,d] 出现的次数分别为 cnt_1,cnt_2,cnt_3，则在 w(a,c)+w(b,d),w(a,d)+w(b,c) 中的贡献分别为 \frac{(cnt_1+cnt_2)(cnt_1+cnt_2-1)}{2}+\frac{(cnt_2+cnt_3)(cnt_2+cnt_3-1)}{2},\frac{(cnt_1+cnt_2+cnt_3)(cnt_1+cnt_2+cnt_3-1)}{2}+\frac{(cnt_2)(cnt_2-1)}{2}，右减左得到 cnt_1 \cdot cnt_3 \geqslant 0。 :::

由此摆上这个简化 LARSCH 算法，初始化每个 f_i 都从 0 继承过来，对于 w(l,r) 的更新，以加入一个元素 a_r 为例，记原来区间 (l,r) 中 a_r 的数量为 cnt_{a_r}，则区间 (l,r] 中令 cnt_{a_r} 加 1，贡献为原来的 cnt_{a_r}。移动 l 同理。减去同理。

代码实现

#include<iostream>
using namespace std;
constexpr int N=500005;
int n,a[N],b[N],p[N];
long long f[N];
struct pointer{
    int l=1,r,cnt[N];
    long long sum;
    void move(int L,int R){
        while(L<l)sum+=cnt[a[--l]]++;
        while(r<R)sum+=cnt[a[++r]]++;
        while(l<L)sum-=--cnt[a[l++]];
        while(R<r)sum-=--cnt[a[r--]];
    }
}t1,t2;
void solve(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    for(int i=p[l-1];i<=p[r];i++){
        t1.move(i+1,mid);
        long long w=f[i]+b[mid]+t1.sum;
        if(w<f[mid])f[mid]=w,p[mid]=i;
    }
    solve(l,mid);
    for(int i=l;i<=mid;i++){
        t2.move(i+1,r);
        long long w=f[i]+b[r]+t2.sum;
        if(w<f[r])f[r]=w,p[r]=i;
    }
    solve(mid+1,r);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        t1.move(1,i);
        f[i]=b[i]+t1.sum;
    }
    solve(1,n);
    for(int i=1;i<=n;i++)cout<<f[i]<<' ';
    return 0;
}

AC 记录。