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

· · 题解

简化 LARSCH 算法，简单易懂还很好写。

这里假定你已经知道一些基本的决策单调性术语。

显然有 f_i=\min_{j=1}^{i-1}\{f_{j-1}+w(j,i)\}。

$w$ 满足四边形不等式，所以这个 dp 是有决策单调性的，而这个 $w$ 是可以支持 $O(1)$ 像莫队一样移动访问的，记一下每一个数的出现次数即可。所以考虑**简化 LARSCH 算法**。 这个算法流程如下，假设我们现在要算出 $[l,r]$ 的答案，且我们已经算出了 $f_l$ 的决策点和 $f_r$ 在 $[1,l]$ 的决策点的答案： 1. 令 $mid=\lceil\frac{l+r}2\rceil$。 1. 求出 $f_{mid}$ 在 $\operatorname{opt}(l)$ 和 $\operatorname{opt}(r)$ 之间的答案，注意这里的 $\operatorname{opt}(r)$ 是指 $r$ 在 $[1,l]$ 的决策点。 2. 递归 $[l,mid]$。 3. 求出 $r$ 在 $l+1$ 和 $mid$ 之间的决策点。 4. 递归 $[mid,r]

这个东西的正确性是显然的。且这个东西是 O(n\log n) 的。

因为这个东西的第二步和第四步对于每个 i，在这个递归树的每一层最多被访问一次，而递归树层数是 O(\log n) 的。

但是这个 w 要像莫队一样访问，但这个东西对第二步和第四步分别维护莫队后，时间复杂度还是 O(n\log n)。证明和上面类似。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=5e5+5;
int n,a[N],b[N];
int f[N],op[N];

struct node{
    int c[N],res;
    int L=1,R;
    void add(int x){
        x=a[x];
        res+=c[x];
        c[x]++;
    }
    void del(int x){
        x=a[x];
        c[x]--;
        res-=c[x];
    }
    int w(int l,int r){
       while(R<r) add(++R);
        while(L>l) add(--L);
        while(L<l) del(L++);
        while(R>r) del(R--);
        return f[l-1]+res+b[r];
    }
    void chk(int j,int i){
        if(w(j,i)<f[i]){
            f[i]=w(j,i);
            op[i]=j;
        }
    }
}n1,n2;
void calc(int l,int r){
    if(l+1>=r){
        n2.chk(r,r);
        return;
    }
    int mid=l+r>>1;
    for(int i=op[l];i<=op[r];i++) n1.chk(i,mid);
    calc(l,mid);
    for(int i=l+1;i<=mid;i++) n1.chk(i,r);
    calc(mid,r);
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    fill(f+1,f+n+1,1e18);
    n1.chk(1,1),n1.chk(1,n);
    calc(1,n);
    for(int i=1;i<=n;i++) cout<<f[i]<<' ';
    return 0;
}