[CF911G]Mass Change Queries

题目大意：
　　给你一个长度为n的数列a，按顺序进行以下m次操作，每次将区间[l,r]中的所有x变成y，问最后数列是怎样的。

思路：
　　线段树。
　　每个线段树结点上维护当前区间每个数分别会变成多少。时间复杂度O(m log n)。然而比别人Ofast+循环展开+特定指令集的O(nm)暴力还慢。

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,A=;

 int a[N];

 class SegmentTree {

     #define _left <<1

     #define _right <<1|1

     private:

         int val[N<<][A];

         void push_down(const int &p) {

             for(register int i=;i<A;i++) {

                 val[p _left][i]=val[p][val[p _left][i]];

                 val[p _right][i]=val[p][val[p _right][i]];

             }

             for(register int i=;i<=A;i++) val[p][i]=i;

         }

     public:

         void build(const int &p,const int &b,const int &e) {

             for(register int i=;i<A;i++) {

                 val[p][i]=i;

             }

             if(b==e) return;

             const int mid=(b+e)>>;

             build(p _left,b,mid);

             build(p _right,mid+,e);

         }

         void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x,const int &y) {

             if(b==l&&e==r) {

                 for(register int i=;i<A;i++) {

                     if(val[p][i]==x) val[p][i]=y;

                 }

                 return;

             }

             push_down(p);

             const int mid=(b+e)>>;

             if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x,y);

             if(r>mid) modify(p _right,mid+,e,std::max(mid+,l),r,x,y);

         }

         void stat(const int &p,const int &b,const int &e) {

             if(b==e) {

                 a[b]=val[p][a[b]];

                 return;

             }

             push_down(p);

             const int mid=(b+e)>>;

             stat(p _left,b,mid);

             stat(p _right,mid+,e);

         }

     #undef _left

     #undef _right

 };

 SegmentTree t;

 int main() {

     const int n=getint();

     for(register int i=;i<=n;i++) {

         a[i]=getint();

     }

     t.build(,,n);

     for(register int q=getint();q;q--) {

         const int l=getint(),r=getint(),x=getint(),y=getint();

         t.modify(,,n,l,r,x,y);

     }

     t.stat(,,n);

     for(register int i=;i<=n;i++) {

         printf("%d%c",a[i]," \n"[i==n]);

     }

     return ;

 }

　　O(n^2)卡常版本：

 #pragma GCC optimize("Ofast")

 #pragma GCC optimize ("unroll-loops")

 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

 #include<cstdio>

 inline char getint8() {

     register char ch;

     while(!__builtin_isdigit(ch=getchar()));

     register char x=ch^'';

     while(__builtin_isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 inline int getint32() {

     register char ch;

     while(!__builtin_isdigit(ch=getchar()));

     register int x=ch^'';

     while(__builtin_isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 int n,m,l,r;

 char x,y,a[];

 int main() {

     n=getint32();

     for(register int i=;i<n;i++) a[i]=getint8();

     for(register int m=getint32();m;m--) {

         l=getint32(),r=getint32(),x=getint8(),y=getint8();

         for(l--;l<r;l++) {

             if(__builtin_expect(a[l]==x,)) a[l]=y;

         }

     }

     for(register int i=;i<n;i++) {

         printf("%hhu%c",a[i]," \n"[i==n]);

     }

     return ;

 }