自动搬运

查看原文

来自洛谷，原作者为

	Chenhaoxuan **

搬运于2025-08-24 23:16:31，当前版本为作者最后更新于2025-05-30 19:54:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12568 [UOI 2023] An Array and Range Additions

题目大意：

给定一个长度为 $n$ 的整数数组 $a$。每次操作可以选择一个区间加上任意整数。求使数组 $a$ 中所有元素两两不同的最小操作次数。

首先我们先考虑本题的弱化版本：你需要保证 选择的区间两两不交。

这时问题变成了一个简单的贪心。我们从左至右扫描整个序列，每次遇到一个重复的数字，就把序列从这里断开，然后新开一段。最后，我们保留第一段不变，后面每一段加上一个互不相同的数字。容易证明最优性。

如果区间可以重叠呢？我们先钦定 序列中的所有数字必须至少改变一次，考虑如下 $n=3$ 的情形：

容易发现如下的操作方案：

其中 $x$ 远大于 $a_i$，$y$ 远大于 $x$。

考虑如下 $n=5$ 的情形：

下面是一种合理的操作方案：

其中 $x$ 远大于 $a_i$，$y$ 远大于 $x$，$z$ 远大于 $y$。

由此推广，我们可以得到如下一般结论：

• 对于 $n$ 次操作，我们最多让 $2n-1$ 个区间变得不同。

  • 具体实现上，让每次操作依次覆盖 $[1,n],[2,n+1],\cdots, [n,2n-1]$ 这些区间即可。

• 对于 $n$ 个区间，我们至少进行 $\left\lfloor\dfrac{n}{2}\right\rfloor+1$ 次操作才能让它们两两不同。

现在考虑更一般的情形。我们可能会面对答案由若干段的改变构成的情况。下面是一个例子。

这样的答案很难求解。但我们发现：我们可以把两个相邻的两个操作区间合并，如下所示：

把中间的无关数字也“带上”操作，容易发现这样的构造也符合要求。于是存在一种合法的构造方案，只有最前面和最后面的一些位置不改变，中间的数字都要改变。

回到本题。我们首先预处理出 每一个点右侧第一次出现重复数字的位置，记为 $nxt_i$。容易以线性对数的复杂度求出。

然后，我们对于每一个合法的前缀 $[1,l]$，找出一个极长的合法后缀 $[r,n]$。这可以双指针动态维护，总情况数不超过 $n$。我们令这些数字不变。

剩下的就只有求出 $[l+1,r-1]$ 中的最少操作数。这转化为上面 序列中的所有数字必须至少改变一次 的情况。由于我们已经求出了 $nxt$ 数组，我们可以从 $l+1$ 开始，在 $nxt$ 上暴力往后跳直至超过 $r-1$，这样单次查询复杂度是 $\mathcal O(n)$ 的。

而上面的跳跃操作是可以倍增优化的，于是我们可以在 $\mathcal O(n\log n)$ 的时间复杂度内求出每对前后缀的答案。把所有情况的答案取最小值即可。

注意特判不需要操作的情形。

AC 代码：

int n, a[maxn], cnt;
int nxt[maxn][20], ans = 0x3f3f3f3f;
map<int, int> mp;
int query(int l, int r) {
	int res = 1;
	for (int j = 19; j >= 0; j--) {
		if (nxt[l][j] <= r) l = nxt[l][j], res += (1 << j);
	}
	return res / 2 + 1;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	nxt[n + 1][0] = n + 1;
	for (int i = n; i >= 1; i--) {
		nxt[i][0] = nxt[i + 1][0];
		if (mp[a[i]]) nxt[i][0] = min(nxt[i][0], mp[a[i]]);
		mp[a[i]] = i;
	}
	for (int i = 1; i <= 19; i++) {
		for (int j = 1; j <= n + 1; j++) 
			nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
	}
	mp.clear(); int l, r;
	for (r = n; r >= 1; r--) {
		if (!mp[a[r]]) mp[a[r]]++;
		else break;
	}
	if (!r) return 0 * puts("0");
	ans = min(ans, query(1, r)); r++;
	for (l = 1; l <= n; l++) {
		while (mp[a[l]] && r <= n) {
			mp[a[r]]--; r++;
		}
		if (mp[a[l]]) break;
		mp[a[l]] = 1;
		ans = min(ans, query(l + 1, r - 1));
	}
	printf("%d", ans);
	return 0;
}