1483. [HNOI2009]梦幻布丁【平衡树-splay】

Description

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

例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

Input

第一行给出N,M表示布丁的个数和好友的操作次数.

第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,

对于每个操作,

若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.

若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. 0。

n,m<=1000000

Output

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

Sample Input

4 3
1 2 2 1
2
1 2 1
2

Sample Output

3
1

调了一下午终于A掉了qwq……
学会启发式合并后，其实这个题就是裸题了
splay启发式合并，听起来很智能，只不过就是暴力将小splay上的点一个个insert到大splay上
这个题只需要将需要改的颜色的splay合并到目标颜色splay上就好了
（这个程序并没有从小的合并到大的，不过仍然很快，可能是数据太弱了）
只不过程序中有一些小细节需要注意就是了
细节详见code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define N (1000000+100)
  6 using namespace std;
  7 int Size[N],Key[N];//key[i]中存的是编号为i的颜色，用序列的编号大小来建splay，节点里存颜色 
  8 int Father[N],Son[N][2];
  9 int n,m,Root[N],ans,a[N];
 10 int flag;
 11 
 12 int Get(int x){return Son[Father[x]][1]==x;}
 13 void Update(int x){Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1;}
 14 void Clear(int x){Key[x]=Father[x]=Son[x][0]=Son[x][1]=Size[x]=0;}
 15 
 16 void Rotate(int x)
 17 {
 18     int wh=Get(x);
 19     int fa=Father[x],fafa=Father[fa];
 20     Son[fa][wh]=Son[x][wh^1];
 21     Father[fa]=x;
 22     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
 23     Son[x][wh^1]=fa;
 24     Father[x]=fafa;
 25     if (fafa) Son[fafa][Son[fafa][1]==fa]=x;
 26     Update(fa);
 27     Update(x);
 28 }
 29 
 30 void Splay(int x,int &root)
 31 {
 32     for (int fa;fa=Father[x];Rotate(x))
 33         if (Father[fa])
 34             Rotate(Get(fa)==Get(x)?fa:x);
 35     root=x;
 36 }
 37 
 38 void Insert(int x,int color,int &root)
 39 {
 40     if (root==0)
 41     {
 42         Size[x]=1;
 43         Key[x]=color;
 44         root=x;
 45         return;
 46     }
 47     int now=root,fa=0;
 48     while (1)
 49     {
 50         fa=now;now=Son[now][x>now];
 51         if (now==0)
 52         {
 53             Size[x]=1;
 54             Key[x]=color;
 55             Father[x]=fa;
 56             Son[fa][x>fa]=x;
 57             Update(fa);
 58             Splay(x,root);
 59             return;
 60         }
 61     }
 62 }
 63 
 64 void Change(int x,int &root,int color)//唯一需要注意的函数，参数:(被拆的splay的当前节点，合并到的splay的根，需要改成什么颜色)。按中序遍历将要拆的splay一个个拆掉就好 
 65 {
 66     if (Son[x][0]) Change(Son[x][0],root,color);
 67     
 68     int rson=Son[x][1];//因为下面要clear x这个节点的信息，所以事先存一下 
 69     int pre_color=Key[x];//同上 
 70     if (!flag && Key[x]!=Key[x-1]) flag=1+(color==Key[x-1]);//☆如果x是连续序列的开始，就把flag改成1。如果不仅是开始，还能和前一个连起来，flag再加一。(flag在连续序列结束的地方会用到) 
 71     Clear(x);
 72     Insert(x,color,root);//插入到目标splay中 
 73     if (Key[x]==Key[x+1]) ans-=1;//如果当前是连续序列的结束且这个点能和后面的颜色接上，ans--。 
 74     if (Key[x+1]!=pre_color) ans-=flag-1,flag=0;//如果这个点是结束，ans根据开头是否接上判断减不减。flag归零。 
 75     
 76     if (rson) Change(rson,root,color);
 77 }
 78 
 79 int main()
 80 {
 81     scanf("%d%d",&n,&m);
 82     for (int i=1;i<=n;++i)
 83     {
 84         scanf("%d",&a[i]);
 85         if (a[i]!=a[i-1]) ans++;
 86         Insert(i,a[i],Root[a[i]]);
 87     }
 88     int opt,x,y;
 89     for (int i=1;i<=m;++i)
 90     {
 91         scanf("%d",&opt);
 92         if (opt==1)
 93         {
 94           scanf("%d%d",&x,&y);
 95           if (Root[x]==0 || x==y) continue;//如果当前颜色没有节点  或者  这次更改前后的颜色是一样的 就不用做了(因为做了会卡) 
 96           Change(Root[x],Root[y],y);
 97           Root[x]=0;
 98         }
 99         if (opt==2) printf("%d
",ans);
100     }
101 }