自动搬运

查看原文

来自洛谷，原作者为

	262620zzj 逸一时，误一世，以酒忆旧扒衣领

搬运于2025-08-24 22:47:34，当前版本为作者最后更新于2023-09-03 22:51:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先读题后，如果直接按照题目模拟，每次放置新棋子就寻找之前的同一颜色棋子，那么复杂度 $O(n^2)$ 显然超时了，不行。

低复杂度做法

定义最后一个颜色是 $c$ 的棋子的位置是 $last_c$，$1 \sim n$ 扫一遍数组，$i \sim last_{color[i]}$ 区间颜色均为 $color[i]$，并且不会被其他染色操作所影响。

那为什么这样是对的呢？(以下简称 $last_{color[i]}$ 为 $lci$）如果有其他的染色操作影响了 $i \sim lci$ 这个区间的话，设影响该区间的区间为 $l \sim r$。

• 如果 $l>lci$，则 $l \sim r$ 和 $i \sim lci$ 不相交。

• 如果 $l<lci$ 且 $r<lci$，则 $l \sim r$ 被 $i \sim lci$ 覆盖，可以略去。

• 如果 $l<lci$ 且 $r>lci$，则在遍历到 $r$ 之前， $i \sim lci$ 已经将 $l$ 染色，此种情况不可能出现。

综上所述，以此方法将一段区间染色后，区间内棋子不会再改变颜色，这样就可以在每次染色之后直接令 $i=lci+1$，总复杂度 $O(n)$。

最后注意 $A[i]\le10^9$，所以用一个 map 解决下标过大的问题。

代码

#include<cstdio>
#include<map>
using namespace std;
const int N=2e5+5;
int n,color[N];
map<int,int> last; 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&color[i]);
		last[color[i]]=i;
	}
	for(int i=1;i<=n;i++){
		int lci=last[color[i]];
		for(int j=i+1;j<lci;j++)color[j]=color[i];
		i=lci;
	}
	for(int i=1;i<=n;i++)printf("%d\n",color[i]);
	return 0;
}