题目大意

给你 N 个格子，编号为 1 \sim N，它们按照编号从小到大排成一排。最初，编号为 i 的格子被涂上了颜色 i。

现在有 Q 次操作要你按顺序完成，其中每次操作是以下两种之一：

• 1 x c：表示把编号为 x 的格子，以及 x 左边连续一串和编号为 x 的格子颜色相同的那些格子，还有 x 右边连续一串和编号为 x 的格子颜色相同的那些格子，全部涂成颜色 c。
• 2 c：输出当前颜色为 c 的格子的个数。

思路

赛时硬控我一直到结束，最后题目理解出错，思路偏离正解很远很远，第二天再来一看，恍然大悟，拿着第一次的错误代码一调，就过了。不得不说，我还只是一只菜鸡呀，需要多练练。

现在我们回到正题。

其实上，x 还有 x 左边的连续一样颜色以及 x 右边的连续一样颜色，可以看做一个连通块，涂色的时候一起改就是了，是吧？现在你想到了什么？对，就是我们熟悉的并查集！如果你不会并查集，那么请先把 P3367 【模板】并查集做掉并学习完并查集后再来做这道题目。

那么我们要怎么合并这些连通块呢？很简单，记录一下这个连通块的左端点和右端点，因为这道题目很特殊，它的一个连通块定是一个区间。合并的时候，就看看当前这个连通块的左端点左边的那个格子（如果存在），所处的那个集合，可不可以经过这次涂色把它们连成一个连通块。还要看当前这个连通块的右端点右边的那个格子（如果存在），所处的那个集合，是不是也可以经过这次涂色把它们连成一个连通块。这些步骤都可以在进行操作 1 时完成。

操作 2 呢？这只能 O(1) 回答啦！弄一个 cnt 数组记录下呗，还是在操作 1 里涂色的时候更新一下就成啦！

是不是还挺简单滴？

AC 代码

这份代码是加了注释的哟！

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
struct node{int l,r,c;}p[N];
//l 和 r 分别是这个集合的两个端点，c 是这个集合目前的颜色
//当然了，只有在 i 是某个集合的代表物时，p[i] 里的数据才是准的
int n,Q,fa[N],cnt[N];//fa 是父亲，cnt 是每种颜色当前个数
int FF(int u){return fa[u]==u?u:fa[u]=FF(fa[u]);}
//经过了路径压缩的找代表物代码，还用了三目运算符（这个总应该懂吧）缩短代码长度
int main(){
    cin>>n>>Q;
    for(int i=1;i<=n;i++)p[i]={i,i,i},fa[i]=i,cnt[i]=1;//初始化
    while(Q--){
        int opt;cin>>opt;//opt 表示操作编号
        if(opt==1){//如果是操作 1
            int id,co;cin>>id>>co;//输入编号以及颜色
            int fid=FF(id);//首先找到当前这个 id 所在集合的代表物
            cnt[p[fid].c]-=p[fid].r-p[fid].l+1;
            //fid 这个集合的所有格子都不再是这个颜色了，要从 cnt 里减去
            p[fid].c=co;//更换颜色
            cnt[p[fid].c]+=p[fid].r-p[fid].l+1;
            //fid 这个集合的所有格子全都变成这个新的颜色了，cnt 要加上
            if(p[fid].l!=1){//如果存在左边的集合
                int fsm=FF(p[fid].l-1);//左边的集合代表物是谁
                if(p[fid].c==p[fsm].c)fa[fsm]=fid,p[fid].l=p[fsm].l;
                //左边的集合与当前集合颜色相同，合并为一个
            }
            if(p[fid].r!=n){//如果存在右边的集合
                int fbg=FF(p[fid].r+1);//右边的集合代表物是谁
                if(p[fid].c==p[fbg].c)fa[fbg]=fid,p[fid].r=p[fbg].r;
                //右边的集合与当前集合颜色相同，合并为一个
            }
        }
        else{//否则是操作 2
            int c;cin>>c;
            cout<<cnt[c]<<"\n";//直接报告答案即可
        }
    }
    return 0;
}