CFR 794 F. Leha and security system ( Segment Tree )

標ㄐㄧProblem - 794F - Codeforces

題意：
給長度 N 的數列 A。有 Q 筆詢問，分兩種：
1 l r x y：代表要將 A[ l .. r ] 中所有 x 的數位變換成 y
2 l r：代表要輸出 A[ l .. r ] 的總和

制約：
N, Q ≤ 1e5
1 ≤ A[ i ] ≤ 1e9
For query type 1: y != 0

解法：
用線段樹維護區間訊息。具體來說，對一個區間需要維護 cbt[ i ] 代表數位 i 造成的總貢獻。除此之外利用 nxt 做類似於懶標記地維護方式，讓子樹知道哪些變換是要做的。至於標記的衝突如何處理，秉持著「先到先做」的思想就沒事了。

複雜度：
O( N lg N log A )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1 << 17;

int N, Q;
int A[ MAXN ];

struct segt {
  int nxt[ MAXN << 2 ][ 10 ];
  long long cbt[ MAXN << 2 ][ 10 ];
  void push( int t ) {
    for( int r = 0; r < 2; ++r ) {
      static long long nc[ 10 ];
      memset( nc, 0, sizeof( nc ) );
      for( int i = 0; i < 10; ++i ) {
        nc[ nxt[ t ][ i ] ] += cbt[ t << 1 | r ][ i ];
        nxt[ t << 1 | r ][ i ] = nxt[ t ][ nxt[ t << 1 | r ][ i ] ];
      }
      memcpy( cbt[ t << 1 | r ], nc, sizeof( nc ) );
    }
    for( int i = 0; i < 10; ++i ) {
      nxt[ t ][ i ] = i;
    }
  }
  void pull( int t ) {
    for( int i = 0; i < 10; ++i ) {
      cbt[ t ][ i ] = cbt[ t << 1 ][ i ] + cbt[ t << 1 | 1 ][ i ];
    }
  }
  void build( int t, int lb, int rb ) {
    for( int i = 0; i < 10; ++i ) {
      nxt[ t ][ i ] = i;
    }
    if( lb + 1 == rb ) {
      for( int i = A[ lb ], j = 1; i; i /= 10, j *= 10 ) {
        cbt[ t ][ i % 10 ] += j;
      }
      return;
    }
    int mid = lb + rb >> 1;
    build( t << 1, lb, mid );
    build( t << 1 | 1, mid, rb );
    pull( t );
  }
  void update( int t, int lb, int rb, int ql, int qr, int x, int y ) {
    if( qr <= lb or rb <= ql ) return;
    if( ql <= lb and rb <= qr ) {
      cbt[ t ][ y ] += cbt[ t ][ x ];
      cbt[ t ][ x ] = 0;
      for( int i = 0; i < 10; ++i ) {
        if( nxt[ t ][ i ] == x ) {
          nxt[ t ][ i ] = y;
        }
      }
      return;
    }
    push( t );
    int mid = lb + rb >> 1;
    update( t << 1, lb, mid, ql, qr, x, y );
    update( t << 1 | 1, mid, rb, ql, qr, x, y );
    pull( t );
  }
  long long query( int t, int lb, int rb, int ql, int qr ) {
    if( qr <= lb or rb <= ql ) return 0;
    if( ql <= lb and rb <= qr ) {
      long long res = 0;
      for( int i = 0; i < 10; ++i ) {
        res += 1LL * i * cbt[ t ][ i ];
      }
      return res;
    }
    push( t );
    int mid = lb + rb >> 1;
    long long res = query( t << 1, lb, mid, ql, qr ) + query( t << 1 | 1, mid, rb, ql, qr );
    pull( t );
    return res;
  }
} root;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> Q;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
  }
  root.build( 1, 0, N );
  for( int qi = 0; qi < Q; ++qi ) {
    int op;
    cin >> op;
    if( op == 1 ) {
      int L, R, X, Y;
      cin >> L >> R >> X >> Y;
      if( X == Y ) continue;
      --L; // [ L, R )
      root.update( 1, 0, N, L, R, X, Y );
    } else {
      int L, R;
      cin >> L >> R;
      --L; // [ L, R )
      cout << root.query( 1, 0, N, L, R ) << "\n";
    }
  }
  return 0;
}