Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const int inf = 0x3f3f3f3f;
- const int off = ( 1 << 19 );
- const int MAXN = 300005;
- inline int L( int x ) { return ( x ) << ( 1 ); }
- inline int R( int x ) { return L( x ) | ( 1 ); }
- int N, Q;
- int a, b;
- char buff[ MAXN ];
- int s[ MAXN ], top;
- int ap[ MAXN ];
- int who[ MAXN ];
- int t[ off << 1 ];
- int lo, hi, cnt;
- void build( int n ) {
- if( n >= off ) return;
- build( L( n ) ); build( R(n) );
- t[n] = min( t[L(n)], t[R(n)] );
- }
- int _query( int x, int y, int n ) {
- if( x >= hi || y <= lo ) return inf;
- if( x >= lo && y <= hi ) return t[n];
- return min( _query( x, (x+y)>>1, L(n) ), _query( (x+y)>>1, y, R(n) ) );
- }
- inline int query( int x, int y ) {
- lo = x; hi = y+1;
- return _query( 0, off, 1 );
- }
- int main( void )
- {
- scanf( "%s", buff );
- int n = strlen( buff );
- int mark = 0;
- s[top++] = 0;
- who[0] = -1;
- for( int i = 0; i < off; ++i )
- t[i+off] = inf;
- for( int i = 0; i < n; ++i ) {
- if( buff[i] == '(' ) {
- ap[i] = cnt;
- who[++mark] = i;
- s[top++] = mark;
- t[off+cnt++] = mark;
- }
- else {
- --top;
- t[off+cnt++] = s[top-1];
- }
- }
- build( 1 );
- scanf( "%d", &Q );
- for( int i = 0; i < Q; ++i ) {
- scanf( "%d%d", &a, &b ); --a, --b; if( a > b ) swap( a, b );
- printf( "%d\n", who[query( ap[a], ap[b] )]+1 );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement