原题传送

正文

是的这次没有前言了。

没有前牙（确信

好吧这个解法可能也不是很奇怪，不过这至少不是老师讲的正解，我赛场上看到题的第一反应就是这个解法。

首先看到题我们很容易就能想到，单独看每一次操作，如果前面有与 $a_i$ 相同石子，我们就应该找到最近的，然后把区间内的颜色都改成 $a_i$。区间修改显然用线段树即可，找到前面第一个与 $a_i$ 相同的石子，预处理不太靠谱，因为有可能会被之前的操作给覆盖掉。于是我想到了栈（你用链表啥的也可以）。

对每种颜色都维护一个栈，从栈底到栈顶一次存了每一个颜色相同的石子的位置，栈顶存的就是当前最近的相同颜色的石子的位置，而每一次操作就在从自己的位置到栈顶的这段区间里修改颜色。但这就出现了两个问题：

一是，也许栈顶的位置早就被之前的操作改成别的颜色去了，我们的修改就错了。怎么办呢，既然错的就 pop 掉就是了，在线段树中单点查询栈顶的位置是否还是和 $a_i$ 一样的颜色，如果不是直接 pop 掉即可，直到栈顶的位置就是 $a_i$ 或者栈空了（也就是前面没有与 $a_i$ 颜色相同的石子了），这时如果栈不空，栈顶就是距离 $a_i$ 最近的颜色相同的石子的位置了。

但第二个问题是，每次线段树区间修改的时候，我们难道要把所有的修改过的位置都放到栈里吗？显然如果放所有的肯定会 T 掉，这很容易构造出来。那我们如果只放其中的一个点呢？如果在下一次用到它之前没有被别的操作修改掉，只放一个显然是对的，如果被修改了，显然异色的石子不会存在于这次修改掉的区间之中，也就是如果被修改，只会将这一串全部都改掉，不会出现只改了一半导致栈里存的东西出错的情况！所以我们存其中的任意一个石子的位置即可，为了使下一次修改的范围尽量的小，我们存这次修改的区间最右边的点即可。

这就是整体的思路，反正很自然的就能顺下来，至少我觉得比老师讲的正解容易想（也有可能是我积累的太少了）。那么这个算法的复杂度是多少呢，我们对着代码来看，为了方便观看，线段树的部分稍微压了点行：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Node{int l,r,zhi;}tr[N*4];
int gai[N*4],a[N];
Node Merge(Node a,Node b){return {a.l,b.r,max(a.zhi,b.zhi)};}//合并节点
void bud(int l,int r,int u){//建树
	if(l==r){tr[u]={l,r,a[l]};return;}
	bud(l,(l+r)/2,u*2);bud((l+r)/2+1,r,u*2+1);
	tr[u]=Merge(tr[u*2],tr[u*2+1]);
}
void lazy(int u){//懒修改
	gai[u*2]=gai[u];gai[u*2+1]=gai[u];
	tr[u*2].zhi=gai[u];tr[u*2+1].zhi=gai[u];gai[u]=0;
}
int cha(int l,int u){//单点查询
	if(tr[u].l==l&&tr[u].r==l)return tr[u].zhi;lazy(u);
	if(l<=(tr[u].l+tr[u].r)/2)return cha(l,u*2);
	else if(l>(tr[u].l+tr[u].r)/2)return cha(l,u*2+1);
}
void g(int l,int r,int u,int d){//区间修改
	if(l<=tr[u].l&&tr[u].r<=r){tr[u].zhi=d;gai[u]=d;return;}lazy(u);
	if(r<=(tr[u].l+tr[u].r)/2)g(l,r,u*2,d);
	else if(l>(tr[u].l+tr[u].r)/2)g(l,r,u*2+1,d);	
	else{g(l,r,u*2,d);g(l,r,u*2+1,d);}tr[u]=Merge(tr[u*2],tr[u*2+1]);
}
//========以上都是可爱的线段树========
int main(){
	int n;cin>>n;
	vector<int>lsh(n+1);int llen=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lsh[++llen]=a[i];
	}
	sort(lsh.begin()+1,lsh.end());
	llen=unique(lsh.begin()+1,lsh.end())-lsh.begin()-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh.begin()+1,lsh.begin()+llen+1,a[i])-lsh.begin();
	}
	//以上是O(n log n)的离散化
	bud(1,n,1);
	vector<stack<int>>z(llen+1);//这是栈不是数组
	z[a[1]].push(1);
	for(int i=2;i<=n;i++){
		while(z[a[i]].size()&&cha(z[a[i]].top(),1)!=a[i])z[a[i]].pop();
		//显然我们最多会执行n次push的操作，因此总共pop的次数也不会超过n
		if(z[a[i]].empty()){//如果前面没有颜色相同的石子
			z[a[i]].push(i);//存进栈里这次操作就完事了
			continue;
		}
		g(z[a[i]].top(),i,1,a[i]);//log的复杂度区间修改[top,i]范围内石子的颜色
		z[a[i]].pop();
		z[a[i]].push(i);//原来的栈顶不要了,只存最新的石子就够了了
	}
	for(int i=1;i<=n;i++){
		cout<<lsh[cha(i,1)]<<endl;
		//一定要记得把离散化后的结果转换回去,别问我怎么知道的!
	}
	return 0;
}

所以，整个程序的时间复杂度就是 $O(n log n)$。

总结

• 一些题的思路顺其自然的就能想下来，遇到问题就分情况讨论来解决问题。
• 像线段树这种模版一定要背熟了，赛场上可没时间让你来调这难调的线段树。
• 一定要记得把离散化后的结果转换成离散化之前的数！
• 没了
• 没了

一点也不大的完~