LGP3201 [HNOI 2009] 梦幻布丁 学习笔记
\(\texttt{Luogu Link}\)
前言
能启发你学会启发式合并的入门题。
题意简述
给定一个长 \(n\) 的序列 \(A\)。请完成 \(m\) 个操作，分为两种：
1 x y：对于所有 \(a_i=x\) 的 \(i\)，将 \(a_i\) 替换为 \(y\)。2：询问序列现在由多少个极长同色连续段组成。
\(n,m\le 10^5\)，\(a_i,x,y\le 10^6\)。
做法解析
一个操作带来的影响是什么？首先，颜色 \(x\) 全部变成颜色 \(y\)，意味着对于拥有该颜色的下标集合，\(S_x\) 并入 \(S_y\)；然后，对于答案来说，答案只少不多，对于每一个原来形如 \(yyxx\) 或 \(xxyy\) 的结构（也即每一个 \(x\) 和 \(y\) 的邻接）答案会减少 \(1\)。
挺简单，不是吗？我们直接维护这个下标集合 \(S_i\)，然后对于每次修改，先统计 \(x\) 和 \(y\) 的邻接次数，再合并它们。为了保证时间复杂度我们启发式地做：对着小集合里的每一个下标 idx 查大集合里面 .count(idx+1) 和 .count(idx-1)，让小的集合往大的里面并。
好这就做完了。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5,MaxV=1e6+5;
int N,M,ans,A[MaxN],Opt,X,Y;
set<int> S[MaxV];
int main(){readis(N,M);for(int i=1;i<=N;i++)readi(A[i]),ans+=(A[i]!=A[i-1]),S[A[i]].insert(i);for(int i=1;i<=M;i++){readi(Opt);if(Opt==1){readis(X,Y);if(X==Y)continue;if(S[X].size()>S[Y].size())swap(S[X],S[Y]);for(int k : S[X])ans-=(S[Y].count(k+1)+S[Y].count(k-1));for(int k : S[X])S[Y].insert(k);S[X].clear();}if(Opt==2)writil(ans);}return 0;
}
后记
当然，这道题不需要线段树来合并。但是信息更复杂的时候就需要了。就比如 \(\texttt{LGP11193}\)。