学习自 在线决策单调性地皮还能单老哥分治做？ - 洛谷专栏
决策单调性最为常用的为分治和二分队列，前者要求离线，后者必须快速处理两个位置的转移，都有一定的局限性，其他算法大部分码量较长，很难应用。
但我们还有一种好写且能维护复杂转移的写法， 简易版 LARSCH 算法，一种能够维护在线转移的分治做法。
丐版 LARSCH 算法
设我们要计算的 \(dp\) 数组为 \(f\) ，考虑如何通过分治维护出在线的转移，既然要求在线，如果在处理 \(i\) 之前能够处理出 \([1,i-1]\) 之间的所有 \(f\) 数组转移一定是正确的，但显然是无法做到的。但分治结构有一个特点，我们可以选择先递归左侧，再递归右侧，也就是对于分治区间 \([l,r]\) 我们能够保证 \([1,l]\) 的 \(f\) 值都是正确的。
我们考虑设计这样的一个 \(solve(l,r)\) 函数，我们要求 ：
- \([1,l]\) 区间内的转移一定正确
- 只考虑 \([1,l]\) 内的值 \(r\) 的转移正确
\(mid\) 为 \(l,r\) 中点，\(p_l,p_r\) 为 \(l,r\) 当前的转移点，对于 \(solve(l,r)\) 我们依次进行下面的操作：
- 用 \([p_l,p_r]\) 的 \(f\) 更新 \(f_{mid}\)
- 递归处理 \(slove(l,mid)\)
- 用 \([l,mid]\) 的 \(f\) 更新 \(f_r\)
- 递归处理 \(slove(mid+1,r)\)
考虑这样操作的正确性，首先，由决策单调性可知，若只考虑 \([1,l]\) 的转移 \(p_{mid}\) 一定位于 \([p_l,p_r]\) ，那我们在递归 \(solve(l,mid)\) 时，依旧满足一开始的要求。处理完 \([l,mid]\) 之后，我们已经有了 \([0,mid]\) 的正确的 \(f\) 值，我们只要再用 \([l,mid]\) 对 \(r\) 进行转移，那在递归 \(solve(mid+1,r)\) 时依旧满足上述条件。如果我们递归到了叶子节点由定义可知，也就得到了 \([1,i-1]\) 到 \(i\) 的正确转移。
考虑时间复杂度，从一层来看所有拆分出来的区间 \([l,r]\) 的 \([p_l,p_r]\) 拼在一起一定构成一整个序列，每一层的时间也就是 \(O(n)\) 一共由 \(\log\) 层，总的时间杂度即为 \(O(n\log n)\)。而且我们的转移贡献可以用类似莫队的两个指针维护，总的移动次数也是 \(n\log n\) 的。
我们现在就得到了一个融合分治和二分队列两家之长的在线分治做法，完全可以平替前两者且较为好写。
Problem - 868F - Codeforces
应用的板子，可以看出真的很好写。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=1e18;
int n,k,a[N],f[N][22];
struct nod{int L,R,ans,vis[N];void clear(){L=1,R=0;ans=0;for(int i=1;i<=n;i++)vis[i]=0;}int val(int l,int r){while(L<l){vis[a[L]]--;ans-=vis[a[L]];L++;}while(L>l){L--;ans+=vis[a[L]];vis[a[L]]++;}while(R>r){vis[a[R]]--;ans-=vis[a[R]];R--;}while(R<r){R++;ans+=vis[a[R]];vis[a[R]]++;}return ans;}
}S,T;
int trans1(int i,int j,int k){return f[i][k-1]+S.val(i+1,j);}
int trans2(int i,int j,int k){return f[i][k-1]+T.val(i+1,j);}
void slove(int l,int r,int L,int R,int k){if(l==r)return ;int mid=(l+r)>>1,I=0,J=0;for(int i=L;i<=R;i++){if(trans1(i,mid,k)<f[mid][k]){f[mid][k]=trans1(i,mid,k);I=i;}}slove(l,mid,L,I,k);for(int i=l;i<=mid;i++){if(trans2(i,r,k)<f[r][k]){f[r][k]=trans2(i,r,k);J=i;}}slove(mid+1,r,I,max(J,R),k);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)f[i][j]=inf;for(int i=1;i<=k;i++){S.clear();T.clear();slove(1,n,0,0,i);}cout<<f[n][k];return 0;
}