[整体二分]数列切割

• 题意：把长度为n的数列分成m连续段，每段非空且价值为该段内相等的数的不同下标的对数
• 思路：发现转移决策点是有单调性的，因此整体二分决策点。算出范围内的一个mid的决策点，就可以分治下去了。
• code:

#include
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll inf=1e18;
int a[N],n,m,L,R,cnt[N];
ll g[N],f[N],ans;
void Add(int x) {ans+=cnt[a[x]]++;}
void Del(int x) {ans-=--cnt[a[x]];}
ll val(int l,int r) {
	while(Ll)Add(--L);
	while(R>r)Del(R--);
	while(R>1,pos;
	for(int i=L,mn=min(R,mid-1);i<=mn;i++) {
		ll w=g[i]+val(i+1,mid);
		if(w