[HNOI2009] 梦幻布丁
题目描述
\(n\) 个布丁摆成一行，进行 \(m\) 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。
例如，颜色分别为 \(1,2,2,1\) 的四个布丁一共有 \(3\) 段颜色.
数据范围
对于全部的测试点，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a_i ,x, y \leq 10^6\)。
思路：
这个题目有好多种不同的做法。
首先你可以考虑使用最暴力的set去合并，但是我们发现如果单纯两个set去交换，他复杂度是 \(O(n)\) 的，显然我们不接受这样的复杂度。所以我们使用指针来维护。
剩下的就是直接异常暴力的更新答案。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb push_back
#define pt putchar
#define All(a) a.begin(),a.end()
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e6+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n,m;
int a[maxn];
set<int>*s[maxn];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=maxn-5;i++)s[i]=new set<int>;
int cnt=0;
for(int i=1;i<=n;i++){
cnt+=a[i]!=a[i-1];
s[a[i]]->insert(i);
}
while(m--){
int op,x,y;
cin>>op;
if(op==1){
cin>>x>>y;
if(x==y)continue;
if(s[x]->size()>s[y]->size())swap(s[x],s[y]);
for(auto it=s[x]->begin();it!=s[x]->end();it++){
cnt-=s[y]->count(*it-1)+s[y]->count(*it+1);
}
for(auto it=s[x]->begin();it!=s[x]->end();it++){
s[y]->insert(*it);
}
s[x]->clear();
}
else {
cout<<cnt<<endl;
}
}
return 0;
}