P3201 [hnoi2009] dream pudding heuristic merge

P3201 [HNOI2009] Dream pudding Heuristic merging

Ideas ： First initialize the total number of segments $ans$, use $color[i]!=color[i-1]$ Just count . Then we use Linked list This data structure stores the subscripts of each color in the linked list of that color , After processing, each color, that is, each linked list stores the subscript of the color . Then we use heuristic merging , because $n$ The maximum is $2e5$ So the worst complexity is $O(nlogn)$ Acceptable , The core of heuristic merging is that each operation will $size$ Small sets merge into $size$ Large set , But there is a problem that needs special treatment , For example, if $x$ Color becomes $y$ Color , but $x$ Of $size$ Greater than $y$ Of $size$ So how do we deal with it ？ We can use one $p$ Array to store color mapping , If appear $x$ Of $size$ Greater than $y$ Of $size$ The situation of , We just need $swap(p[x],p[y])$ that will do . It means that from now on, we think the original $x$ Color is $y$ Color , The original $y$ Color is $x$ Color .

Code ：

/* * @author: Snow * @Description: Algorithm Contest * @LastEditTime: 2022-07-22 16:22:40 */
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize(3)
typedef pair<int,int>PII;
#define pb emplace_back
int n,m;
const int N = 1e5+10;
const int M = 1e6+10;
int color[M];
int h[M],ne[N],e[N],idx;
int p[M];
int ans;
int sz[M];
void add(int a,int b){
    
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void merge(int &x,int &y){
    // Real time updates should be referenced 
    if(x==y)return ;//x and y May be equal 
    if(sz[x]>sz[y])swap(x,y);
    for(int i=h[x];i!=-1;i=ne[i]){
    
        int j=e[i];
        ans-=(color[j-1]==y)+(color[j+1]==y);
    }
    for(int i=h[x];i!=-1;i=ne[i]){
    
        int j=e[i];
        color[j]=y;
        if(ne[i]==-1){
    
            ne[i]=h[y];
            h[y]=h[x];
            break;
        }
    }
    h[x]=-1;
    sz[y]+=sz[x];
    sz[x]=0;
}
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
    
        cin>>color[i];
        if(color[i]!=color[i-1])ans++;
        sz[color[i]]++;
        add(color[i],i);
    }
    for(int i=1;i<M;i++)p[i]=i;
    while(m--){
    
        int op;
        cin>>op;
        if(op==1){
    
            int x,y;
            cin>>x>>y;
            merge(p[x],p[y]);
        }
        else cout<<ans<<endl;
    }
    return 0;
}