题目描述：
给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列.
数据范围：
\(1\le n\le 2\times 10^5\)
\(1\le a_i\le 100\)
\(1\le q\le 2\times 10^5,1\le l,r\le n,1\le x,y\le 100\)
思路：
观察数据范围，我们发现值域只有可怜的 \(100\)
所以一个想法就诞生了。
我们对于每个节点开 \(100\) 个懒标记，对于每个 \(tg_i\) 都表示 \(i\) 这个数最后变成什么了。
然后随便更新一下就可以了。
点击查看代码
#include<bits/stdc++.h>
#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=2e5+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n,a[maxn];
int Q;
struct node{
int val;
int tg[105];
}tree[maxn<<2];
void build(int l,int r,int i){
for(int k=1;k<=100;k++)tree[i].tg[k]=k;
if(l==r){
tree[i].val=a[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
return ;
}
void push_down(int i){
auto &l=tree[ls],&r=tree[rs];
auto &u=tree[i];
for(int k=1;k<=100;k++){
l.tg[k]=u.tg[l.tg[k]];
r.tg[k]=u.tg[r.tg[k]];
}
for(int k=1;k<=100;k++)u.tg[k]=k;
return ;
}
void update(int l,int r,int L,int R,int x,int y,int i){
if(L<=l&&R>=r){
for(int k=1;k<=100;k++){
if(tree[i].tg[k]==x){
tree[i].tg[k]=y;
}
}
return ;
}
int mid=(l+r)>>1;
push_down(i);
if(L<=mid)update(l,mid,L,R,x,y,ls);
if(R>mid)update(mid+1,r,L,R,x,y,rs);
}
void print(int l,int r,int i){
if(l==r){
cout<<tree[i].tg[tree[i].val]<<" ";
return ;
}
push_down(i);
int mid=(l+r)>>1;
print(l,mid,ls);
print(mid+1,r,rs);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>Q;
build(1,n,1);
while(Q--){
int l,r,x,y;
cin>>l>>r>>x>>y;
update(1,n,l,r,x,y,1);
}
print(1,n,1);
return 0;
}