题意翻译
给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列.
输入输出格式
输入格式:
The first line contains one integer n n n ( 1<=n<=200000 1<=n<=200000 1<=n<=200000 ) — the size of array a a a .
The second line contains n n n integers a1 a_{1} a1 , a2 a_{2} a2 , ..., an a_{n} an ( 1<=ai<=100 1<=a_{i}<=100 1<=ai<=100 ) — the elements of array a a a .
The third line contains one integer q q q ( 1<=q<=200000 1<=q<=200000 1<=q<=200000 ) — the number of queries you have to process.
Then q q q lines follow. i i i -th line contains four integers l l l , r r r , x x x and y y y denoting i i i -th query ( 1<=l<=r<=n 1<=l<=r<=n 1<=l<=r<=n , 1<=x,y<=100 1<=x,y<=100 1<=x,y<=100 ).
输出格式:
Print n n n integers — elements of array a a a after all changes are made.
输入输出样例
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 int c[800001][101]; 8 bool flag[200001][101]; 9 int n,a[200001],ans[200001];10 void build(int rt,int l,int r)11 { int i;12 for (i=1;i<=100;i++)13 c[rt][i]=i;14 if (l==r) return;15 int mid=(l+r)/2;16 build(rt<<1,l,mid);17 build(rt<<1|1,mid+1,r);18 }19 void pushdown(int rt)20 { int i;21 for (i=1;i<=100;i++)22 {23 c[rt<<1][i]=c[rt][c[rt<<1][i]];24 c[rt<<1|1][i]=c[rt][c[rt<<1|1][i]];25 }26 for (i=1;i<=100;i++)27 c[rt][i]=i;28 }29 void update(int rt,int l,int r,int L,int R,int x,int y)30 { int i;31 if (l>=L&&r<=R)32 {33 for (i=1;i<=100;i++)34 if (c[rt][i]==x) c[rt][i]=y;35 return;36 }37 pushdown(rt);38 int mid=(l+r)/2;39 if (L<=mid) update(rt<<1,l,mid,L,R,x,y);40 if (R>mid) update(rt<<1|1,mid+1,r,L,R,x,y);41 }42 void query(int rt,int l,int r)43 {44 if (l==r)45 {46 ans[l]=c[rt][a[l]];47 return;48 }49 int mid=(l+r)/2;50 pushdown(rt);51 query(rt<<1,l,mid);52 query(rt<<1|1,mid+1,r);53 }54 int main()55 { int i,q,l,r,x,y;56 cin>>n;57 for (i=1;i<=n;i++)58 {59 scanf("%d",&a[i]);60 }61 build(1,1,n);62 cin>>q;63 for (i=1;i<=q;i++)64 {65 scanf("%d%d%d%d",&l,&r,&x,&y);66 update(1,1,n,l,r,x,y);67 }68 query(1,1,n);69 for (i=1;i