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

Problem - 380C - Codeforces

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;
}
```