1. 题目

传送门= ̄ω ̄=

[HNOI2009]梦幻布丁

时间限制:10s 空间限制:64MB

题目描述

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

输入格式

第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色,这时你应该输出一个整数. 0

输出格式

针对第二类操作即询问,依次输出当前有多少段颜色.

样例输入

4 3
1 2 2 1
2
1 2 1
2

样例输出

3
1

提示

没有写明提示

题目来源

没有写明来源

补:数据范围:1<=n,m<=100,000; 0<Ai,x,y<1,000,000

2. 做法

前面看到神犇pyh在做这道题,远远望去觉得好水啊——~~用分块或者线段树解决不就行了吗?~~
然而……其实是我看错题了。题目是说把某种颜色的布丁改为另一种颜色,而不是把一个区间的布丁改为另一种颜色……

然而其实这样子更水!= ̄ω ̄=
用启发式合并就可以了!

具体怎么搞呢?

首先,我们搞1,000,000个链表(如果你想用别的容器也随你),再搞个数组color[1000000],其中color[i]表示颜色i所对应的链表下表是color[i]。

然后我们再输入的时候与处理好这些链表和color数组,同时遍历一遍,算出最开始的答案ans。

那链表存什么呢?链表存这个链表对应的颜色的那些节点的下标(在输入的数组中的位置)。

而如果我们要让颜色x变成颜色y,就把颜色x对应的链表复制到颜色y对应的链表后面。对于复制过去的每个元素(每个节点下标)(这些节点的颜色都是x)i,我们判断数组中下表为i-1和i+1的节点颜色是否为y,如果为y那么ans–(因为之前i的颜色一定为x,所以它的颜色一定不为y,所以如果i-1或者i+1为y,那么一定是原来不在一段颜色中的两端合并成了一段)。

有了这个我们就得到了暴力解法,复杂度为:O(mn);

这时候我们可以用启发式合并。
思路很简单:合并两个链表的时候,把长度小的合并到长度大的链表里面去。
乍一看复杂度不会减小多少,但是其实这样复杂度就降到了O(mlogn)。
~~至于为什么我不会证。~~

怎么搞呢?就是在把链表a合并到链表b的时候,如果list[a].size()>list[b].size就swap(color[a],color[b])。这是很显然的。

代码:

#include <cstdio>
#include <cctype>
#include <list>
#include <algorithm>
using namespace std;
template<typename tp>void read(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,arr[100005],root[1000005],ans;
list<int> l[1000005];
void merge(int a,int b)
{
    for(list<int>::iterator i=l[a].begin();i!=l[a].end();i++)
    {
        l[b].push_back(*i);
        if(arr[*i-1]==b)ans--;
        if(arr[*i+1]==b)ans--;
    }
    for(list<int>::iterator i=l[a].begin();i!=l[a].end();i++)arr[*i]=b;
    l[a].clear();
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++)
    {
        read(arr[i]);
        if(arr[i]!=arr[i-1])ans++;
        root[arr[i]]=arr[i],l[arr[i]].push_back(i);
    }
    for(int i=1,a,b;i<=m;i++)
    {
        read(a);
        if(a==2)printf("%d\n",ans);
        else
        {
            read(a),read(b);
            if(a==b)continue;
            if(l[root[a]].size()>l[root[b]].size())swap(root[a],root[b]);
            a=root[a],b=root[b];
            merge(a,b);
        }
    }
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *