CFR 380 C. Sereja and Brackets ( Segment Tree, D&C, Bracket Sequence )

題意：
給一個括弧序列，和若干筆詢問。詢問給 L, R，問原序列的 [ L, R ] 區間裡最常的合法匹配序列 ( 可間斷 ) 多長。

資料規模：
序列長度 ≤ 1e6
詢問數 ≤ 1e5

解法：
考慮基於分治的預處理。如果我們知道一個區間分別的最長合法匹配序列長度; 未使用的左括弧數量; 未使用的右括弧數量，便足以正確更新。詳見代碼。

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

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

const int MAXN = ( int ) 1e6 + 5;

struct segt{
  int maxlen[ MAXN << 3 ], unlb[ MAXN << 3 ], unrb[ MAXN << 3 ]; // unused left / right bracket
  void pull( int t ){
    int newb = min( unlb[ t << 1 ], unrb[ t << 1 | 1 ] );
    maxlen[ t ] = maxlen[ t << 1 ] + maxlen[ t << 1 | 1 ] + newb;
    unlb[ t ] = unlb[ t << 1 ] + unlb[ t << 1 | 1 ] - newb;
    unrb[ t ] = unrb[ t << 1 ] + unrb[ t << 1 | 1 ] - newb;
  }
  template< class T >
  void build( int t, int lb, int rb, const T &arr ){
    if( lb + 1 == rb ){
      if( arr[ lb ] == '(' ) unlb[ t ] = 1;
      else unrb[ t ] = 1;
      return;
    }
    int mid = lb + rb >> 1;
    build( t << 1, lb, mid, arr );
    build( t << 1 | 1, mid, rb, arr );
    pull( t );
  }
  tuple< int, int, int > query( int t, int lb, int rb, int ql, int qr ){
    if( qr <= lb or rb <= ql ) return make_tuple( 0, 0, 0 );
    if( ql <= lb and rb <= qr ) return make_tuple( maxlen[ t ], unlb[ t ], unrb[ t ] );
    int mid = lb + rb >> 1;
    auto tl = query( t << 1, lb, mid, ql ,qr );
    auto tr = query( t << 1 | 1, mid, rb, ql, qr );
    int a, b, c; tie( a, b, c ) = tl;
    int x, y, z; tie( x, y, z ) = tr;
    int nb = min( b, z );
    return make_tuple( a + x + nb, b + y - nb, c + z - nb );
  }
} tree;

string seq;

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> seq;
  tree.build( 1, 0, seq.size(), seq );
  int M; cin >> M;
  for( int mi = 0; mi < M; ++mi ){
    int ql, qr; cin >> ql >> qr; --ql; // [ ql, qr )
    cout << 2 * get< 0 >( tree.query( 1, 0, seq.size(), ql, qr ) ) << "\n";
  }
  return 0;
}