Brief description:

略。）

Analysis:

启发式合并 + 链表）

（。。如果手写链表的话。。可以删去中间已经没用的格子。。只保留联通块左右？。）

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9, M = int(1e6) + 9;

int a[N], p[M]; VI adj[M];
int n, m, z;

#define px p[x]
#define py p[y]

void Merge(){
    int x, y; RD(x, y); if (x == y) return; //if (px == py) return;
    if (!px) return;

    if (!py){
        py = px;
        px = 0;
        return;
    }

    if (SZ(adj[px]) > SZ(adj[py])) swap(px, py);

    ECH(it, adj[px]){
        if (a[*it-1] == py) --z;
        if (a[*it+1] == py) --z;
        adj[py].PB(*it);
    }

    ECH(it, adj[px]) a[*it] = py;
    CLR(adj[px]); px = 0;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); REP_1(i, n){
        adj[RD(a[i])].PB(i), p[a[i]] = a[i];
        if (a[i] != a[i-1]) ++z;
    }

    DO(m){
        if (RD() == 1){
            Merge();
        }
        else{
            OT(z);
        }
    }
}

Posted by xiaodao
Category: 日常
Tags: 启发式合并