Codeforces Round #438F: Yet Another Minimization Problem

http://codeforces.com/problemset/problem/868/F

良問of良問だと思う。

まず簡単なdpから考えて、dp(i,j):=j番目までの数列をiコに分割した時の最小コスト、と定義すれば
dp(i,j)=min(dp(i-1,j')+cost(j',j1))でできます。この時dp(i,j)が最小値となるj'をp(j)と表すと、
dp(i,j1), dp(i,j2)(j1p(j2)を仮定すると、コストが優モジュラー性(cost(x+i+j)-cost(x+i)>=cost(x+i)-cost(i)つまり、要素が多いほど要素を加えた時の変化も大きくなる)を有するので、cost(p(j2),j2)+cost(p(j1),j1)>=cost(p(j2),j1)+cost(p(j1),j2)が成立します。また、
dp(i,j2)が最小なので、dp(i-1,p(j2))+cost(p(j2)+j2)cost(p(j2)+j2)-cost(p(j1),j2)>=cost(p(j2),j1)-cost(p(j1),j1)となり、
dp(i,j1)=dp(i-1,p(j1))+cost(p(j1),j1)>dp(i-1,p(j2))+cost(p(j2),j1)となりますが、これはj1のとき最小であることと矛盾するので示せました。

単調性を有するdpの一般的なテクとして分割統治法があります。
真ん中の要素をとって、それに対する遷移をO(N)で全部試します。真ん中の要素から右左と潜ればO(NlogN)になるというテクニックです。
例としては
https://online.acmicpc.org/problems/money
とかです。

最後にcost(l,r)を求めたいのですが、これは真ん中の要素をmとすれば、[p(m),m)の区間から値を加えたり削除したりを区間の長さに等しい計算量だけ行えば、その区間についての必要なcostは求まるので、奈良市計算量O(1)です。

int N, K;
int lv, rv;
int A[MAX_N];
int C[200010];
ll dp[30][200010];
ll S;

void add(int v) {
	S += C[A[v]];
	C[A[v]]++;
}

void sub(int v) {
	C[A[v]]--;
	S -= C[A[v]];
}

void query(int l, int r) { //[lv, rv)to[l, r)
	while(lv < l) sub(lv++);
	while(lv > l) add(--lv);
	while(rv > r) sub(--rv);
	while(rv < r) add(rv++);
}

void loop(int l, int r, int pl, int pr, int k) { //[l, r) and [pl, pr)
	int m = (l + r) / 2;
	int at = 0;
	for(int i = min(m, pr); i >= pl; i--) {
		query(i, m);
		if(dp[k + 1][m] >= S + dp[k][i]) {
			at = i;
			dp[k + 1][m] = S + dp[k][i];
		}
	}
	if(r - l <= 1) return;
	loop(l, m, pl, at, k);
	loop(m + 1, r, at, pr, k);
}

void solve() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];
	S = 0; lv = 0; rv = 0;
	dp[1][0] = linf;
	rep(i, 1, N + 1) {
		query(0, i);
		dp[1][i] = S;
	}
	rep(k, 1, K) rep(i, 0, N + 1) dp[k + 1][i] = linf;
	rep(i, 1, K) loop(0, N + 1, 0, N + 1, i);
	cout << dp[K][N] << "\n";
}

dp,優モジュラー性、単調性、分割統治法といろいろ問題を構成する要素があって楽しい。
Endagorion先生流石です。と思ったけどどうやら典型らしい…。