題意：
給出一個數列,有q個操作,每種操作是把區間[l,r]中等于x的數改成y.輸出q步操作完的數列.
題解：
100個數，很容易想到要從這里進行突破，對于某次操作我們只需要把這個區間的數x給移動到y的這個數的集合里面不就可以了，線段樹合并！
這樣的話我們對于每一種顏色動態開一個線段樹，合并就把顏色為x的線段樹區間l r合并到顏色為y的線段樹的區間l r 上即可，
之前大多數的線段樹合并是整顆線段樹進行合并，這個是針對于某段區間進行合并，我們需要稍微調整一下這個update即可，
最后只需要遍歷一遍這100棵線段樹然后把有值的位置存到ans陣列里面最后輸出即可，
代碼：
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int maxn=2e7+10;
#define endl '\n'
int rt[110];
int ls[maxn],rs[maxn];
int cnt;
//bool tree[maxn];
void ins(int &node,int start,int ends,int pos){
if(!node) node=++cnt;
if(start==ends){
//tree[node]=true;
return ;
}
int mid=(start+ends)/2;
if(pos<=mid) ins(ls[node],start,mid,pos);
else ins(rs[node],mid+1,ends,pos);
//push(node);
}
int mer(int x,int y){
if(!x||!y) return x+y;
ls[x]=mer(ls[x],ls[y]);
rs[x]=mer(rs[x],rs[y]);
return x;
}
void update(int &x,int &y,int start,int ends,int l,int r){ //y合并到x
if(!y) return ;
if(l<=start&&ends<=r){
x=mer(x,y);y=0;
return ;
}
if(!x) x=++cnt; //x如果沒有需要開辟新的結點
int mid=(start+ends)/2;
if(l<=mid) update(ls[x],ls[y],start,mid,l,r);
if(mid<r) update(rs[x],rs[y],mid+1,ends,l,r);
}
int ans[200010];
void query(int node,int start,int ends,int val){
if(node==0) return ;
if(start==ends){
ans[start]=val;
return ;
}
int mid=(start+ends)/2;
query(ls[node],start,mid,val);
query(rs[node],mid+1,ends,val);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
ins(rt[x],1,200000,i);
}
int q;
cin>>q;
while(q--){
int l,r,x,y;
cin>>l>>r>>x>>y;
if(x==y) continue;
update(rt[y],rt[x],1,200000,l,r);
}
for(int i=1;i<=100;i++){
query(rt[i],1,200000,i);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/286793.html
標籤：其他