[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)

发布于 2018-02-05  103 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)

Description

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.
例如颜色分别为1,2,2,1的四个布丁一共有3段颜色

Http

BZOJ
Luogu

Tag

平衡树,启发式合并

解决思路

震惊,某选手手写平衡树调一晚上没有调过,一怒之下竟然用\(set\)水过。
对每一种颜色维护一个平衡树存储有那些位置是这个颜色,那么把一种颜色改成另一种颜色的时候,就启发式地把两个合并。全局维护一个答案,若把这个点加入会少一些答案,那么直接减去即可。
但需要注意的是,题中明确说是把\(x\)合并到\(y\),但我们启发式合并的时候可能是把\(y\)合并到\(x\),这时候我们就把\(x\)与\(y\)的编号永久地交换一下,让以后找到\(x\)都相当于找到了\(y\),\(y\)同理。
没错,这一题可以用\(set\)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1001000;
const int inf=2147483647;

int n,Ans=0;
int Col[maxN],Colf[maxN];
set<int> S[maxN];

void Merge(int u,int v);

int main()
{
    int m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=1000000;i++) Colf[i]=i;//这个就是标记当前颜色真实对应到的颜色编号
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&Col[i]);
        if (Col[i]!=Col[i-1]) Ans++;
        S[Col[i]].insert(i);
    }
    while (m--)
    {
        int opt;scanf("%d",&opt);
        if (opt==1)
        {
            int u,v;scanf("%d%d",&u,&v);
            if (u==v) continue;//相等直接跳过
            if (S[Colf[u]].size()>S[Colf[v]].size()) swap(Colf[u],Colf[v]);//保证启发式合并
            Merge(Colf[u],Colf[v]);
        }
        if (opt==2) printf("%d\n",Ans);
    }
    return 0;
}

void Merge(int u,int v)
{
    for (set<int>::iterator i=S[u].begin();i!=S[u].end();i++)
    {
        if (Col[*i-1]==v) Ans--;//当加入这个位置会减少答案,则减少
        if (Col[*i+1]==v) Ans--;
        S[v].insert(*i);
    }
    for (set<int>::iterator i=S[u].begin();i!=S[u].end();i++)//统一修改标记
        Col[*i]=v;
    S[u].clear();//清空
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1483/Luogu3201][HNOI2009]梦幻布丁(平衡树,启发式合并)


HNCJ OIer