TIOJ 1952 小向的試煉 3-3：鑰匙 ( Segment Tree, Tags )

1952 - 小向的試煉 3-3：鑰匙(Key) | TIOJ INFOR Online Judge

題意：
給一個長度為 N 的字串，接著 M 筆詢問。詢問 L, R, K 代表 [ L, R ] 的字母要按照字典序大到小( K = 0 ) 或小到大( K = 1 )排序。求所有操作後的字串長相。

資料規模：
第一行有兩個正整數N≤1e5,M≤50000，分別代表鑰匙的區塊數以及希爾伯特敲擊鑰匙的次數。
第二行有一個長度為N的字串，代表鑰匙原料的初始狀態。所有字元都是英文小寫字母。
接下來有M行，每行有三個整數1≤i≤j≤N,0≤k≤1，代表這次敲擊讓第i個字元(含)一直到第j個字元(含)重新排列(編號由1編號到N)。如果k=1就代表由小排到大，k=0代表由大排到小。

解法：
考慮只有兩種字符的情形，那麼很直覺的做法是用線段樹維護一個區間裡有多少個第一種的字符，將該區間清空後，再把這個數量在前綴( 或後綴，看 K )做區間加值 +1。現在有 26 種字符，只是變成要開 26 棵線段樹。這裡我用兩種標籤維護，tag 代表區間加值的標籤，ctag 代表區間清空( 全部設為 0 )。

時間 / 空間複雜度：
O( N lg N )

注意：
打兩個 tag 的時候，要做好兩個 tag 衝撞時的處理。這裡保證做完清空操作後，加值標籤一定是零，所以當清空標籤和加值標籤同時存在時，一定是清空先處理。然後其實可以不要用兩個 tag，讓 ctag 支援變成任何一種數字即可。

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

const int MAXN = ( int ) 1e5;

int N, M;
string seq;

struct Segment_Tree{
  int sum[ MAXN << 3 ];
  int tag[ MAXN << 3 ];
  int ctag[ MAXN << 3 ];
  void push( int t, int lb, int rb ){
    if( ctag[ t ] ){
      ctag[ t << 1 ] = ctag[ t << 1 | 1 ] = 1;
      sum[ t << 1 ] = sum[ t << 1 | 1 ] = 0;
      tag[ t << 1 ] = tag[ t << 1 | 1 ] = 0;
      ctag[ t ] = 0;
    }
    int mid = lb + rb >> 1;
    sum[ t << 1 ] += ( mid - lb ) * tag[ t ];
    tag[ t << 1 ] += tag[ t ];
    sum[ t << 1 | 1 ] += ( rb - mid ) * tag[ t ];
    tag[ t << 1 | 1 ] += tag[ t ];
    tag[ t ] = 0;
  }
  void pull( int t ){
    sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
  }
  void update( int t, int lb, int rb, int ql, int qr, int v ){
    if( qr <= lb or rb <= ql ) return;
    if( ql <= lb and rb <= qr ){
      if( ctag[ t ] ){
        if( lb + 1 < rb ){
          ctag[ t << 1 ] = ctag[ t << 1 | 1 ] = 1;
          sum[ t << 1 ] = sum[ t << 1 | 1 ] = 0;
          tag[ t << 1 ] = tag[ t << 1 | 1 ] = 0;
        }
        ctag[ t ] = 0;
      }
      sum[ t ] += ( rb - lb ) * v;
      tag[ t ] += v;
      return;
    }
    push( t, lb, rb );
    int mid = lb + rb >> 1;
    update( t << 1, lb, mid, ql, qr, v );
    update( t << 1 | 1, mid, rb, ql, qr, v );
    pull( t );
  }
  int 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 ) return sum[ t ];
    push( t, lb, rb );
    int mid = lb + rb >> 1;
    int res = query( t << 1, lb, mid, ql, qr )
            + query( t << 1 | 1, mid, rb, ql, qr );
    pull( t );
    return res;
  }
  void clear( int t, int lb, int rb, int ql, int qr ){
    if( qr <= lb or rb <= ql ) return;
    if( ql <= lb and rb <= qr ){
      ctag[ t ] = 1;
      tag[ t ] = 0;
      sum[ t ] = 0;
      return;
    }
    push( t, lb, rb );
    int mid = lb + rb >> 1;
    clear( t << 1, lb, mid, ql, qr );
    clear( t << 1 | 1, mid, rb, ql, qr );
    pull( t );
  }
} segt[ 26 ];

void build( int z, int t, int lb, int rb, const string &seq ){
  if( lb + 1 == rb ){
    segt[ z ].sum[ t ] = seq[ lb ] - 'a' == z;
    return;
  }
  int mid = lb + rb >> 1;
  build( z, t << 1, lb, mid, seq );
  build( z, t << 1 | 1, mid, rb, seq );
  segt[ z ].pull( t );
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  cin >> seq;
  for( int i = 0; i < 26; ++i ){
    build( i, 1, 0, N, seq );
  }
  for( int i = 0; i < M; ++i ){
    int ql, qr, k; cin >> ql >> qr >> k; --ql; // [ ql, qr )
    vector< int > cnt( 26 );
    for( int j = 0; j < 26; ++j ){
      cnt[ j ] += segt[ j ].query( 1, 0, N, ql, qr );
      segt[ j ].clear( 1, 0, N, ql, qr );
    }
    if( k == 0 ){
      int lp = ql; // last puttable position
      for( int j = 26 - 1; j >= 0; --j ){
        segt[ j ].update( 1, 0, N, lp, lp + cnt[ j ], 1 );
        lp += cnt[ j ];
      }
    } else{
      int lp = ql;
      for( int j = 0; j < 26; ++j ){
        segt[ j ].update( 1, 0, N, lp, lp + cnt[ j ], 1 );
        lp += cnt[ j ];
      }
    }
  }
  string ans;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < 26; ++j ){
      if( segt[ j ].query( 1, 0, N, i, i + 1 ) ){
        ans += ( char ) ( 'a' + j );
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}