题目链接：点我啊╭(╯^╰)╮
题目大意：
n n n 个数字，分为 k k k 段
使每段内相同数字的对数 的和最小
解题思路：
d p [ i ] [ k ] dp[i][k] dp[i][k] 为以 i i i 为止，分为 k k k 段的最小值
发现随着 i i i 的增大，满足决策单调性
设区间 ( x , y ) (x, y) (x,y) 的答案位置在 ( l , r ) (l, r) (l,r)
则可以进行类似整体二分的转移
对于修改，可以用莫队处理，复杂度均摊
核心：决策单调在整体二分上的应用
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 1e5 + 5;
int n, k, a[maxn], nl = 1, nr;
ll dp[maxn][25], cnt[maxn], sum;inline void add(int x){x = a[x];if(cnt[x]) sum -= cnt[x] * (cnt[x] - 1) / 2;cnt[x]++;if(cnt[x]) sum += cnt[x] * (cnt[x] - 1) / 2;
}inline void del(int x){x = a[x];if(cnt[x]) sum -= cnt[x] * (cnt[x] - 1) / 2;cnt[x]--;if(cnt[x]) sum += cnt[x] * (cnt[x] - 1) / 2;
}inline void gao(int ql, int qr){while(ql < nl) add(--nl);while(ql > nl) del(nl++);while(qr < nr) del(nr--);while(qr > nr) add(++nr);
}void solve(int l, int r, int x, int y, int k){if(l > r || x > y) return;int mid = x + y >> 1, pos;ll mi = 1e18;for(int i=l; i<=min(mid, r); i++){gao(i, mid);ll tmp = dp[i-1][k-1] + sum;if(tmp < mi){dp[mid][k] = mi = tmp;pos = i;}}solve(l, pos, x, mid-1, k);solve(pos, r, mid+1, y, k);
}int main() {scanf("%d%d", &n, &k);for(int i=1; i<=n; i++) scanf("%d", a+i);for(int i=1; i<=n; i++) gao(1, i), dp[i][0] = sum;for(int i=1; i<k; i++)solve(1, n, 1, n, i);printf("%lld\n", dp[n][k-1]);
}