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;
}