fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll; 
  6. typedef long double ld;
  7. typedef vector<ll> vec; 
  8. typedef vector<vector<ll>> vec2;
  9. typedef pair<ll,ll> pair1;
  10. typedef pair<string,ll> pair2;
  11. typedef pair<ll,string> pair3;
  12. typedef pair<string,string> pair4;
  13. #define fl(i,a,b) for(i=a;i<b;i++)
  14. #define rfl(i,a,b) for(i=b-1;i>=a;i--)
  15. #define f first
  16. #define s second
  17.  
  18. int a[100005];
  19.  
  20. set<ll> seg[4*100005],final;
  21.  
  22. void build(ll ind,ll low,ll high)
  23. {
  24.     if(low==high){
  25.         if(a[low]%2==0)
  26.         seg[ind].insert(a[low]);
  27.         return;
  28.     }
  29.  
  30.     ll mid=(low+high)>>1;
  31.  
  32.     build(2*ind+1,low,mid);
  33.     build(2*ind+2,mid+1,high);
  34.  
  35.     seg[ind].insert(seg[2*ind+1].begin(),seg[2*ind+1].end());
  36.     seg[ind].insert(seg[2*ind+2].begin(),seg[2*ind+2].end());
  37. }
  38.  
  39. void query(ll ind,ll low,ll high,ll l,ll r)
  40. {
  41.     if(low>=l&&high<=r){
  42.         final.insert(seg[ind].begin(),seg[ind].end());
  43.         return;
  44.     }
  45.  
  46.     if(high<l||low>r) return;
  47.     ll mid=(low+high)>>1;
  48.  
  49.     query(2*ind+1,low,mid,l,r);
  50.  
  51.     query(2*ind+2,mid+1,high,l,r);
  52. }
  53.  
  54. int main() 
  55. {
  56.     ios_base::sync_with_stdio(false); 
  57.     cin.tie(NULL);
  58.  
  59.     string s;cin>>s;
  60.  
  61.     ll n=s.length(),i;
  62.     fl(i,0,n) a[i]=s[i]-96;;
  63.  
  64.     build(0,0,n-1);
  65.  
  66.     ll q;cin>>q;
  67.  
  68.     while(q--)
  69.     {
  70.         ll l,r; cin>>l>>r;
  71.  
  72.         query(0,0,n-1,l-1,r-1);
  73.  
  74.         cout<<final.size()<<"\n";
  75.  
  76.         final.clear();
  77.     }
  78.     return 0;
  79. }
Success #stdin #stdout 0.02s 22388KB
comments (?)
stdin
copy 
bbccdd
5
1 2
3 4
5 6
1 6
2 5
stdout
copy 
1
0
1
2
2
https://ideone.com/461E9M
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!