题解：P17210 【模板】半在线决策单调性
yinianxingkong
·
·
题解
先讲本题的弱化版：CF868F Yet Another Minimization Problem，唯一的区别是那题有个 k。
不多说明这个 w(l,r) 的决策单调性。由于转移只需要上一层的 dp 值，可以分治：设 solve(l,r,pl,pr) 表示处理区间 [l,r] 决策点在 [pl,pr] 的情况。
然后就是这个 w(l,r) 不好快速求。考虑用莫队，就是说直接双指针维护变化量。由于每一层的移动都不会超过区间长度，总的移动距离就是 O(n\log n) 的。
本题去掉了 k，相当于要半在线地做上述问题。
有这么一个科技：简易版 LARSCH 算法。
具体原理可以看上述文章的分析，这里简述一下流程。
在 `solve(l,r)` 时，区间 $(l,r]$ 满足 $[0,l]$ 的 $f_i$ 已经求出，且使用 $[0,l]$ 的 $f_i$ 更新了 $f_r$。取 $mid=\lfloor \frac{l+r}{2} \rfloor$ 依次进行：
1. 用 $[p_l,p_r]$ 的 $f_i$ 更新 $f_{mid}$。
2. 递归 `solve(l,mid)`。
3. 用 $(l,mid]$ 的 $f_i$ 更新 $f_r$。
4. 递归 `solve(mid+1,r)`。
逻辑是自洽的。复杂度方面，对第一步和第三步分别考虑，都相当于把整个序列跑一遍，所以复杂度是 $O(n\log n)$。
所以求 $w(l,r)$ 需要开**两个莫队**，分别维护决策点和当前区间的点的求值。
代码实现如下，比较简短：
```cpp
int n,a[N],b[N],p[N];ll f[N];
struct MoTeam{
int l,r,tong[N];ll val;
MoTeam(){l=1,r=0,val=0;}
ll w(int ql,int qr){
if(ql>qr)return 0;
val-=b[r];
while(r<qr)val+=tong[a[++r]]++;
while(l>ql)val+=tong[a[--l]]++;
while(r>qr)val-=--tong[a[r--]];
while(l<ql)val-=--tong[a[l++]];
val+=b[r];
return val;
}
void chk(int j,int i){ll W=f[j]+w(j+1,i);if(W<f[i])f[i]=W,p[i]=j;}
}A,B;
void solve(int l,int r){
if(l+1==r)return;int mid=l+r>>1;
for(int j=p[l];j<=p[r];j++)A.chk(j,mid);
solve(l,mid);
for(int j=l+1;j<=mid;j++)B.chk(j,r);
solve(mid,r);
}
signed main(){
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++)f[i]=INF;
A.chk(0,n),solve(0,n);
for(int i=1;i<=n;i++)cout<<f[i]<<' ';
return 0;
}
```