返回首页

【HNOI2009】梦幻布丁 题解

我是题目链接

题解

·不要管标签上面的“Treap”还有“线段树”，这题最简单的方法是链表的启发式合并

·我们像链式前向星(Mr.Zhou管它叫“边目录集”)一样，建立一个next数组，next[i]表示上一个颜色为i的布丁出现的位置，next数组的维护方式也是一样的，建立一个h数组，h[i]表示最后一个颜色为i的布丁出现的位置

·这样我们就弄出了若干条链表

·我们考虑修改操作会怎样影响最终答案

·对于一个位置pos，如果它发生改变，使得它与左边那个元素相同了，说明它原来与左边那个不同（废话！），也就是说原来这里对答案有1的贡献，现在贡献没了，因此发生这种情况答案要-1，右边同理

·合并时我们将短的链合到长的链里面，这样单次操作时间复杂度就是O(短链长度)，合并时只要沿着链遍历一遍，把路过的元素给改了，然后再搞一下链头链尾什么的就好了

·那么问题来了，对于一个把x改成y的操作，如果x链是短链好办，直接把x链合并到y链就行。但如果x链是长链呢？把y链合并到x链不就变成把y改成x了吗？

·没关系，就算我们就把y改成x，你出题人又能怎么样？打我啊？

·对于这种情况，记一个数组def，def[i]表示颜色i被你合到哪里去了，以后对所有元素进行合并时，我们用def数组就行了。def数组的初值设为def[i]=i

·这不好理解，打个比方，出题人要你合并x、y，然后合并y、z，你发现y是短链，然后你把y合到x里面去了，此时记def[y]=x，接下来合并y、z就等价于合并x、z，也就是def[y]、def[z]

·细节参考代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=100000,MAXM=1000000;
int a[MAXN+5],n,m;
int nxt[MAXN+5],h[MAXM+5];
int sz[MAXM+5];
int def[MAXM+5];
int ans=1;

void merge(int &x,int &y)
{
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	int p=0;
	for(int i=h[x];i;i=nxt[i])
	{
		ans-=(a[i-1]==y)+(a[i+1]==y);
		if(!nxt[i]){p=nxt[i]=h[y];h[y]=h[x];break;}
	}
	for(int i=h[x];i!=p;i=nxt[i]) a[i]=y;
	h[x]=0;sz[y]+=sz[x];sz[x]=0;
}

int main()
{
	int opt,x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		nxt[i]=h[a[i]];
		h[a[i]]=i;
		sz[a[i]]++;
	}
	for(int i=2;i<=n;i++)
		if(a[i]!=a[i-1]) ans++;
	for(int i=1;i<=MAXM;i++) def[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&opt);
		if(opt==2) printf("%d\n",ans);
		else{scanf("%d%d",&x,&y);merge(def[x],def[y]);}
	}
	return 0;
}