首页 > > 程序设计 > C/C++ >

洛谷P3201 [HNOI2009]梦幻布丁

2018-06-17 21:29:01来源：未知阅读 ()

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

3
1

说明

1<=n,m<=100,000; 0<Ai,x,y<1,000,000

用N个平衡树维护这N个颜色出现的位置

就本题而言，完全可以用一个set水过

每次合并的时候暴力合并就可以

注意当读入的颜色相同的时候直接跳出

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<ctime>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<set>
 8 using namespace std;
 9 #define ls T[now].ch[0]
10 #define rs T[now].ch[1]
11 const int MAXN=1e6+10;
12 inline char nc()
13 {
14     static char buf[MAXN],*p1=buf,*p2=buf;
15     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
16 }
17 inline int read()
18 {
19     char c=nc();int x=0,f=1;
20     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
21     while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
22     return x*f;
23 }
24 set<int>s[MAXN];
25 int a[MAXN],f[MAXN],ans;
26 void unionn(int x,int y)
27 {
28     for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++)
29     {
30         if(a[*i-1]==y)  ans--;
31         if(a[*i+1]==y)    ans--;
32         s[y].insert(*i);
33     }
34     for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++)
35         a[*i]=y;
36     s[x].clear();
37 }
38 int main()
39 {
40     #ifdef WIN32
41     freopen("a.in","r",stdin);
42     #else
43     #endif
44     int n=read(),m=read();
45     for(int i=1;i<=n;i++)
46     {
47         a[i]=read();
48         if(a[i]!=a[i-1]) ans++;
49         f[a[i]]=a[i];
50         s[a[i]].insert(i);
51     }
52     while(m--)
53     {
54         int opt=read();
55         if(opt==2)    { printf("%d\n",ans);continue;}
56         int a=read(),b=read();
57         if(a==b)    continue;
58         if(s[f[a]].size()>s[f[b]].size())    swap(f[a],f[b]);
59         unionn(f[a],f[b]);
60     }
61     return 0;
62 }