CWOI S C0297C on

題意

U2FsdGVkX1+iGGcgnVGDR50qrY2/famzvdIJPHcDzBVzZJhRLBp940h3Ko01EEzw
dCJe5/clYmT54g7H2/jN11PfwmzHsyfCtE/EnJ3119dqExNBpE5hpA/UOudhV1AB
Wp4YKeE+LcFn4cAoEiDzxtuecW/dqGc6NXI8s/PKm7Q8rImznQ8UkFe41HlHylAr
hvTmL1KvuLMAkpNy1eXas90kpOW2lM5YYqixSjHkvgTzvjSFl+jVIQD2C3H5Dc/E
W3YrJqB1IWjlS5UlfQZeQ4QhZwtFPETJKxz1qysPhO7i1Iw19dT3GQUnZR6g08xL
ac3fuBQKqrLua+XZP6OHa3naTH/qtrGtsUTLoQOjqZb5qxLFftV2Jj8cnFLRf31S
F24QjiX+pb733NDW76dtIwccekiuxy9tkjVC27EsucP31HV2LO/RnLYXGjGOb2EA
WIx6UNrcQXdplDorxJ0GXm9w4p0dX+/66EJBYXghFA4nZiojXMheuon87/Bvqcsq
wK8it8lO4qMRjc3lmEXy1Y/AT4QcE28IuS44HC0tGNJhebTM8PEdFEgHKAlGOLPS
AFFrC5LIUrDsfj5kM/F+LaUSYozdUnqkTKC8gxOtUfx59A2z4YCJ4DN44v+m+8Ce
UE4hsJUF2vLaRUJzyAtgJjxCq/gKb4uLPNG0TBNDFVKNfZ0n5SM08pMVdHhkkLNd
2n7Ay589OUqqSNoZ0z6knOl26lyDCkdYGwarY+bZ67NUknajcOXDUzNkpFHOq2xV
gDsWjFTpbvDIMnLQfj04ZcH7D6/HPOKd2NdJoKFXA+8ov7iHTuDOnASMu3K0RcAt
dC18WYSrCXIj3r1UhZO+MTM2qG987vPuzxvHy0JKRXEq0Bk7t6/C3UrMQfFZcdJM
Z1JiDqEIde9wcY75J+sDGgthFMrnxIBn2ahZpo3eM7Y=

解析

先忽略掉第 $k$ 次的額外代價。對於任意一對 $(i, j)$，如果他們在某次操作中產生了貢獻，那麼他們一定是本來在個連續端中，後來被分開了，所以任意一對 $(i, j)$ 只會產生一次貢獻。同時經過 $n-1$ 次操作之後，$a$ 被分成 $n$ 段，即任意一對 $(i, j)$ 不可能在同一段，也就是每一對 $(i, j)$ 已經做過了貢獻。因此，分割的方法、順序不能影響最終的貢獻，且最終的貢獻就是：

$$\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} a_{i} a_{j}$$

接下來考慮第 $k-1$ 次的額外代價。問題轉化為將長度為 $n$ 的序列分割成 $k$ 段，最小化上面的代價式子。設 $f(i, j)$ 表示分成 $i$ 段，考慮前 $j$ 個元素的最小代價，容易得到轉移方程：

$$f(i, j) = \min_{0 \le k \le j} \{f(i - 1, k) + w(k, j)\}$$

來分析一下 $w(l, r)$ 的性質。對於 $q(l, r)$，可以寫成：

$$q(l, r) = \sum_{i=l}^{r} \sum_{j=l}^{r} [a_{l} = a_{r}]$$

設 $l_{1} \le l_{2} \le r_{1} \le r_{2}$。比較 $q(l_{1}, r_{1}) + q(l_{2}, r_{2})$ 和 $q(l_{1}, r_{2}) + q(l_{2}, r_{1})$ 的大小關係。考慮每一對 $(i, j)$ 滿足 $a_{i}=a_{j}$ 的貢獻：

• 如果 $i, j \in [l_{2}, r_{1})$，那麼兩個式子都要多上 $2$ 的貢獻。
• 如果 $i$，$j$ 中有且僅有一個在 $[l_{2}, r_{1})$ 中，兩個式子都多上 $1$ 的貢獻。
• 如果 $i$，$j$ 中沒有在 $[l_{2}, r_{1})$ 中的，則前者沒有貢獻，後者多 $1$ 的貢獻。

綜上，有 $q(l_{1}, r_{1}) + q(l_{2}, r_{2}) \le q(l_{1}, r_{2}) + q(l_{2}, r_{1})$，即 $q$ 滿足四邊形不等式。然後注意到 $\sum_{j=l+1}^{r-1} \left[|a_{j} -a_{j+1}| + \left(a_{j} \oplus a_{j+1}\right)\right]$ 顯然滿足四邊形恆等式，所以 $w(l, r)$ 滿足四邊形不等式，$f(i, j)$ 滿足決策單調性，可以分治計算。

最後，如何快速計算 $w(l, r)$？可以用類似莫隊的思想，容易發現，左右端點的移動次數是 $O(n\log n)$ 級別的。

實現

constexpr int sqr(int x) { return x * x; }

int main()
{
	set_io("on");

	int n, k, h;
	std::cin >> n >> k >> h;
	std::vector<int> a(n), cc(n), cca(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		cc[i] = a[i];
	}
	std::sort(cc.begin(), cc.end());
	cc.erase(std::unique(cc.begin(), cc.end()), cc.end());
	int m = cc.size();
	for (int i = 0; i < n; i++) {
		cca[i] = std::lower_bound(cc.begin(), cc.end(), a[i]) - cc.begin();
	}

	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans += a[i] * a[j];
		}
	}

	if (h == 0) {
		std::cout << ans << std::endl;
		return 0;
	}

	auto get_cost = [&a, &cca, m](int l, int r)
	{
		static long long q = 0;
		static long long sum = 0;
		static int ll = 0, rr = 0;
		static std::vector<int> exist(m);

		if (ll == rr) ll = rr = l;

		while (rr < r) {
			if (rr - ll >= 1) sum += std::abs(a[rr] - a[rr - 1]) + (a[rr] ^ a[rr - 1]);
			q -= sqr(exist[cca[rr]]);
			exist[cca[rr]]++;
			q += sqr(exist[cca[rr]]);
			rr++;
		}

		while (l < ll) {
			ll--;
			if (rr - ll >= 2) sum += std::abs(a[ll] - a[ll + 1]) + (a[ll] ^ a[ll + 1]);
			q -= sqr(exist[cca[ll]]);
			exist[cca[ll]]++;
			q += sqr(exist[cca[ll]]);
		}

		while (r < rr) {
			rr--;
			if (rr - ll >= 1) sum -= std::abs(a[rr] - a[rr - 1]) + (a[rr] ^ a[rr - 1]);
			q -= sqr(exist[cca[rr]]);
			exist[cca[rr]]--;
			q += sqr(exist[cca[rr]]);
		}

		while (ll < l) {
			if (rr - ll >= 2) sum -= std::abs(a[ll] - a[ll + 1]) + (a[ll] ^ a[ll + 1]);
			q -= sqr(exist[cca[ll]]);
			exist[cca[ll]]--;
			q += sqr(exist[cca[ll]]);
			ll++;
		}

		return q * sum;
	};

	std::vector<long long> f(n + 1, std::numeric_limits<long long>::max() / 2);
	std::vector<long long> g(n + 1);
	f[0] = 0;
	for (int i = 0; i < k; i++) {
		std::fill(g.begin(), g.end(), std::numeric_limits<long long>::max() / 2);
		auto solve = [&f, &g, &get_cost](auto &&self, int l, int r, int pl, int pr) -> void
		{
			int mid = l + (r - l) / 2;
			int p = l;
			for (int i = pl; i < mid && i <= pr; i++) {
				long long w = f[i] + get_cost(i, mid);
				if (g[mid] > w) {
					p = i;
					g[mid] = w;
				}
			}
			if (l < mid) self(self, l, mid - 1, pl, p); 
			if (mid < r) self(self, mid + 1, r, p, pr);
		};
		solve(solve, 0, n, 0, n);
		std::swap(f, g);
	}

	std::cout << ans + f[n] << std::endl;
}