codefroces 911G Mass Change Queries

题意翻译

给出一个数列,有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： 复制

5

1 2 3 4 5

3

3 5 3 5

1 5 5 1

1 5 1 5

输出样例#1： 复制

5 2 5 4 5

维护100颗线段树$c[rt][i]=j$，表示在这个区间里i颜色变成j

区间修改，将修改下传

初始$c[rt][i]=i$

至于下传状态：

$c[L(rt)][i]=c[rt][c[L(rt)][i]]$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int c[800001][101];
bool flag[200001][101];
int n,a[200001],ans[200001];
void build(int rt,int l,int r)
{int i;
  for (i=1;i<=100;i++)
    c[rt][i]=i;
  if (l==r) return;
  int mid=(l+r)/2;
  build(rt<<1,l,mid);
  build(rt<<1|1,mid+1,r);
}
void pushdown(int rt)
{int i;
  for (i=1;i<=100;i++)
    {
      c[rt<<1][i]=c[rt][c[rt<<1][i]];
      c[rt<<1|1][i]=c[rt][c[rt<<1|1][i]];
    }
  for (i=1;i<=100;i++)
    c[rt][i]=i;
}
void update(int rt,int l,int r,int L,int R,int x,int y)
{int i;
  if (l>=L&&r<=R)
    {
      for (i=1;i<=100;i++)
    if (c[rt][i]==x) c[rt][i]=y;
      return;
    }
  pushdown(rt);
  int mid=(l+r)/2;
  if (L<=mid) update(rt<<1,l,mid,L,R,x,y);
  if (R>mid) update(rt<<1|1,mid+1,r,L,R,x,y);
}
void query(int rt,int l,int r)
{
  if (l==r)
    {
      ans[l]=c[rt][a[l]];
      return;
    }
  int mid=(l+r)/2;
  pushdown(rt);
  query(rt<<1,l,mid);
  query(rt<<1|1,mid+1,r);
}
int main()
{int i,q,l,r,x,y;
  cin>>n;
  for (i=1;i<=n;i++)
    {
      scanf("%d",&a[i]);
    }
  build(1,1,n);
  cin>>q;
  for (i=1;i<=q;i++)
    {
      scanf("%d%d%d%d",&l,&r,&x,&y);
      update(1,1,n,l,r,x,y);
    }
  query(1,1,n);
  for (i=1;i<n;i++)
    printf("%d ",ans[i]);
  cout<<ans[n]<<endl;
}