Solution

第一眼看上去就像一个用并查集维护的题。想了下发现的确如此。

具体地，对于操作 1，我们分解为如下两个操作：

1. 将当前 x 所在的同颜色连通块整体改成颜色 c。
2. 更改颜色后，判断这个连通块的颜色分别和左右两边连通块的颜色是否相同，如果相同就合并成一个连通块。

发现上述两个操作可以用并查集维护（具体见代码和注释），操作 2 直接输出当前颜色集合的大小即可。

Code

#include<bits/stdc++.h>
#define int long long 
#define ull unsigned long long
#define ri register int
#define rep(i,j,k) for(ri i=(j);i<=(k);++i) 
#define per(i,j,k) for(ri i=(j);i>=(k);--i)
#define repl(i,j,k,l) for(ri i=(j);(k);i=(l))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pc(x) putchar(x)
#define fir first
#define se second 
#define MP pair<int,int>
#define pii pair<int,int>
#define PB push_back
#define lson p << 1
#define rson p << 1 | 1
#define ls(p) tr[p].ch[0]
#define rs(p) tr[p].ch[1]
using namespace std;
char BUFFER[100000],*P1(0),*P2(0);
#define gtc() (P1 == P2 && (P2 = (P1 = BUFFER) + fread(BUFFER,1,100000,stdin), P1 == P2) ? EOF : *P1++)
inline int R(){
    int x;char c;bool f = 0;
    while((c = gtc()) < '0') if(c == '-') f = 1;
    x = c ^ '0';
    while((c = gtc()) >= '0') x = (x << 3) + (x << 1) + (c ^ '0');
    return f?(~x + 1):x;
}
inline string Rs(){
    string str = "";
    char ch = gtc();
    while(ch == ' ' || ch == '\n' || ch == '\r') ch = gtc();
    while(ch != ' ' && ch != '\n' && ch != '\r' && ch > '\0') str += ch, ch = gtc();
    return str;
}
inline int rS(char s[]){
    int tot = 0; char ch = gtc();
    while(ch == ' ' || ch == '\n' || ch == '\r') ch = gtc();
    while(ch != ' ' && ch != '\n' && ch != '\r' && ch > '\0') s[++tot] = ch, ch = gtc();
    return tot; 
}
inline void O(int x){
    if(x < 0) pc('-'),x = -x;
    if(x < 10) pc(x + '0');
    else O(x / 10),pc(x % 10 + '0');
}
inline void out(int x,int type){
    if(type == 1) O(x),pc(' ');
    if(type == 2) O(x),pc('\n');
    if(type == 3) O(x);
}
inline void Ps(string s, int type){
    int m = s.length();
    rep(i, 0, m - 1) pc(s[i]); 
    if(type == 1) pc(' ');
    if(type == 2) pc('\n');
}
inline void pS(char *s, int type){
    int m = strlen(s + 1);
    rep(i, 1, m) pc(s[i]);
    if(type == 1) pc(' ');
    if(type == 2) pc('\n');
}
inline void OI(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
const int N = 5e5 + 10;
int fa[N], n, q, siz[N], col[N], l[N], r[N];
// l[]: 一个同颜色连通块的左端点， r[]: 一个同颜色连通块的右端点
int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
inline void solve(){
    n = R(), q = R();
    rep(i, 1, n) fa[i] = l[i] = r[i] = col[i] = i, siz[i] = 1;
    while(q--){
        int opt = R();
        if(opt == 1){
            int x = R(), c = R();
            int fx = find(x); //找出 x 所在的一个同颜色连通块
            if(col[fx] == c) continue;
            siz[col[fx]] -= r[fx] - l[fx] + 1; //由于颜色改变，这个连通块原本的颜色的集合大小要减去这个连通块的大小
            col[fx] = c, siz[c] += r[fx] - l[fx] + 1;//然后更改颜色，并将新颜色集合的大小加上这个连通块的大小
            if(l[fx] > 1){ //如果有机会合并左边的连通块
                int fy = find(l[fx] - 1); //找到左边这个点所在的连通块
                if(col[fx] == col[fy]) fa[fy] = fx, l[fx] = l[fy]; //如果两个连通块颜色相同，合并成一个连通块
            }
            if(r[fx] < n){ //同理
                int fy = find(r[fx] + 1);
                if(col[fx] == col[fy]) fa[fy] = fx, r[fx] = r[fy]; 
            }
        }else{
            int c = R();
            out(siz[c], 2);//查询一种颜色集合的大小。
        }
    }
}
signed main(){
    // OI();
    int T = 1;
    // T = R();
    while(T--) solve();
    return 0;
}