题目描述

$N$个布丁摆成一行,进行$M$次操作。

每次将某个颜色的布丁全部变成另一种颜色的,询问当前一共有多少段颜色。

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

输入格式

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

第二行$N$个数$A1,A2...An$表示第$i$个布丁的颜色。

从第三行起有$M$行,对于每个操作:

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

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

输出格式

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

样例输入

4 3
1 2 2 1
2
1 2 1
2

样例输出

3
1

数据范围

$1<=n,m<=100,000$ $0<Ai,x,y<1,000,000$

菜鸡的咆哮

这是一道模拟题,用$Vector$瞎搞一下就可以$AC$了。

$num[i]$记录每个布丁的颜色。

$pos[i]$记录颜色为$i$的布丁的位置。

因为颜色的范围很小,我们甚至不需要离散$QwQ$。

依次模拟颜色变换的过程,并更新答案。

将下标为$i$的颜色$X$变为$Y$后:

若$num[i-1]=num[i+1]$

​ ①$X$与左右颜色相同,$Y$与左右颜色不同 变化后段数$+2$

​ ②$X$与左右颜色不同,$Y$与左右颜色相同 变化后段数$-2$

若$num[i-1] \neq num[i+1]$

​ ①$X$与左右颜色不同,$Y$与左右颜色之一不同 变化后段数$-1$

​ ②$X$与左右颜色之一不同,$Y$与左右颜色相同 变化后段数$+1$

注意更新$num$和$pos$数组。

代码

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,m,ans;
int num[maxn];
vector<int> pos[maxn];
int main(){
    scanf("%d%d",&n,&m);
    memset(num,0x3f,sizeof(num));
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        pos[num[i]].push_back(i);
        if(num[i]-num[i-1]) ans++;
    }
    int opt;
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&x,&y);
            if(x==y) continue;
            for(int i=0;i<pos[x].size();i++){
                int xx=pos[x][i];
                if(num[xx-1]==num[xx+1]){
                    if(x==num[xx-1]&&y!=num[xx-1]) ans+=2; 
                    if(x!=num[xx-1]&&y==num[xx-1]) ans-=2;
                } 
                else{
                    if(x!=num[xx-1]&&x!=num[xx+1]&&(y!=num[xx-1]||y!=num[xx+1])) ans--;
                    if((x!=num[xx-1]||x!=num[xx+1])&&y!=num[xx-1]&&y!=num[xx+1]) ans++;
                }
                num[xx]=y;
                pos[y].push_back(xx);
            }
            pos[x].clear();
        }
        else printf("%d\n",ans);
    }
    return 0;
}