沧州企业网站建设,宿迁房价,毕业设计网站开发类题目,wordpress 萝莉梦幻布丁
金牌导航 启发式合并-1
luogu 3201
题目大意
有若干个布丁#xff0c;给出它们的颜色#xff0c;每次将一个颜色的所有布丁变成另一种颜色#xff0c;然后询问有多少段连续的数
输入样例
4 3
1 2 2 1
2
1 2 1
2输出样例
3
1样例解释
初始时布丁颜色依次为 …梦幻布丁
金牌导航 启发式合并-1
luogu 3201
题目大意
有若干个布丁给出它们的颜色每次将一个颜色的所有布丁变成另一种颜色然后询问有多少段连续的数
输入样例
4 3
1 2 2 1
2
1 2 1
2输出样例
3
1样例解释
初始时布丁颜色依次为 1,2,2,1三段颜色分别为 [1,1], [2,3], [4,4] 一次操作后布丁的颜色变为1,1,1,1只有[1,4]一段颜色
数据范围
1⩽n,m⩽105,1⩽ai,x,y⩽1061 \leqslant n, m \leqslant 10^5,1 \leqslant a_i ,x, y \leqslant 10^61⩽n,m⩽105,1⩽ai,x,y⩽106
提示
请注意不保证颜色的编号不大于 n也不保证 x≠yx \neq yxym 不是颜色的编号上限
解题思路
如果每次暴力查询时间O(nm)O(nm)O(nm)会TLETLETLE 对于每次合并考虑把小的合并到大的中这样可以有效降低时间 对于集合AAA如果和BBB合并(∣A∣⩽∣B∣)(|A|\leqslant|B|)(∣A∣⩽∣B∣)那么AAA所在集合大小变为∣A∣∣B∣|A||B|∣A∣∣B∣变大了一倍所以集合∣A∣|A|∣A∣最多合并lognlognlogn次nnn个集合时间为O(nlogn)O(nlogn)O(nlogn) 对于更改颜色可以用一个b数组存下第i种颜色存在第几个颜色中这样可以O(1)实现交换两个子集就可以使小的合并到大的中
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
using namespace std;
int n, m, x, y, ans, s[N*10], b[N*10], st[N*10], nx[N], head[N*10], color[N];
void add(int x, int y)//加入点
{b[x] x;//初始存在自己if (!head[x]) st[x] y;//第一条边nx[y] head[x];head[x] y;s[x];
}
void solve(int x, int y)
{for (int i head[x]; i; i nx[i]){if (y color[i - 1]) ans--;//相同就合并了数量-1if (y color[i 1]) ans--;}for (int i head[x]; i; i nx[i])color[i] y;//、、变色s[y] s[x];//累加nx[st[y]] head[x];//连在该子集后面st[y] st[x];head[x] s[x] st[x] 0;
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d, color[i]);if (color[i] ! color[i - 1]) ans;add(color[i], i);}while(m--){scanf(%d, x);if (x 2) printf(%d\n, ans);else{scanf(%d%d, x, y);if (x y) continue;if (s[b[x]] s[b[y]]) swap(b[x], b[y]);//小的合并到大的if (!s[b[x]]) continue;solve(b[x], b[y]);}}return 0;
}
