网站建设广告平台推广,建设工程信息查询,美工设计培训网,网络赣州正题
题目链接:https://www.luogu.com.cn/problem/P3201 题目大意
开始有nnn个布丁#xff0c;第iii个是cic_ici颜色的。 每次有操作
将所有颜色为xxx的布丁变为颜色yyy的。询问有多少个布丁颜色段。 解题思路
对于每次修改#xff0c;我们可以考虑启发式合并#xff…正题
题目链接:https://www.luogu.com.cn/problem/P3201 题目大意
开始有nnn个布丁第iii个是cic_ici颜色的。 每次有操作
将所有颜色为xxx的布丁变为颜色yyy的。询问有多少个布丁颜色段。 解题思路
对于每次修改我们可以考虑启发式合并将小的合并到大的上面我们可以用类似于链表的结构维护每个颜色的所有布丁。修改后直接将数量少的合并到数量大的上面即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int n,m,ans,fa[N],a[N],siz[N];
int ls[N],st[N],next[N];
void Merge(int x,int y){for(int ils[x];i;inext[i])ans-(a[i-1]y)(a[i1]y);for(int ils[x];i;inext[i])a[i]y;next[st[x]]ls[y];ls[y]ls[x];siz[y]siz[x];ls[x]siz[x]st[x]0;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);fa[a[i]]a[i];ansa[i]!a[i-1];if(!st[a[i]])st[a[i]]i;siz[a[i]];next[i]ls[a[i]];ls[a[i]]i;}for(int i1;im;i){int op,x,y;scanf(%d,op);if(op1){scanf(%d%d,x,y);if(xy)continue;if(siz[fa[x]]siz[fa[y]])swap(fa[x],fa[y]);if(!siz[fa[x]])continue;Merge(fa[x],fa[y]);}else printf(%d\n,ans);}return 0;
}
