ulvis.paste.net

Paste Search Dynamic
Recent pastes
build_tree
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long N=2e5+5;
  4. const long long inf=1e9+7;
  5. long long ope[N];
  6. long long clo[N];
  7. long long diff[N];
  8. long long node[N*4];
  9. void build_tree(long long id, long long l, long long r){
  10.         //cout << l << " "  << r<<endl;
  11.         if(l==r){
  12.                 node[id]=diff[l];
  13.                 return;
  14.         }
  15.         long long mid=(l+r)/2;
  16.         build_tree(id*2,l,mid);
  17.         build_tree(id*2+1,mid+1,r);
  18.         node[id] = max(node[id*2] , node[id*2+1]);
  19. }
  20. long long get(long long id, long long l, long long r, long long u, long long v){
  21.         if(r<u||l>v){
  22.                 return -inf;
  23.         }
  24.         if(l>=u&&r<=v){
  25.                 return node[id];
  26.         }
  27.         long long mid=(l+r)/2;
  28.         return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
  29. }
  30. signed main(){
  31.         ios_base::sync_with_stdio(0);
  32.         cin.tie(0);
  33.         string s;
  34.         cin >> s;
  35.         long long q;
  36.         cin >> q;
  37.         long long n = (s.size()/2);
  38.         ope[2*n+1]=0;
  39.         clo[2*n+1]=0;
  40.         for(int i=n*2;i>=1;i--){
  41.                 if(s[i-1]=='('){
  42.                         ope[i]=ope[i+1]+1;
  43.                         clo[i]=clo[i+1];
  44.                 }
  45.                 else if(s[i-1]==')'){
  46.                         ope[i]=ope[i+1];
  47.                         clo[i]=clo[i+1]+1;
  48.                 }
  49.                 diff[i]=clo[i]-ope[i];
  50.         }
  51.         build_tree(1,1,n*2);
  52.         /*
  53.         for(int i=1;i<=n*8;i++){
  54.                 cout << node[i]<< " ";
  55.         }
  56.         cout <<endl;
  57.         for(int i=1;i<=n*2;i++){
  58.                 cout << ope[i] << " ";
  59.         }
  60.         cout<< endl;
  61.         for(int i=1;i<=n*2;i++){
  62.                 cout << clo[i] << " ";
  63.         }
  64.         cout << endl;
  65.         for(int i=1;i<=n*2;i++){
  66.                 cout << diff[i]<< " ";
  67.         }
  68.         cout << endl;
  69.         */
  70.         while(q--){
  71.                 long long a,b;
  72.                 cin >> a >> b;
  73.                 long long ans=get(1,1,n*2,a,b);
  74.                 //cout << ans<<endl;
  75.                 long long OPE=n-ope[a];
  76.                 long long CLO=n-clo[a];
  77.                 //cout << ans<< " " << OPE<< " " << CLO<<endl;
  78.                 long long DIFF=CLO - OPE;
  79.                 ans = ans+DIFF;
  80.                 if(ans<=0){
  81.                         cout << "YES"<<endl;
  82.                 }
  83.                 else{
  84.                         cout<< "NO"<<endl;
  85.                 }
  86.         }
  87. }
Parsed in 0.012 seconds