fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int N, Q, type;
  6. string inp ;
  7. int ST[380000] ;
  8.  
  9.  
  10. inline void build(int low, int high, int pos){
  11.  
  12.     if(low==high){
  13.  
  14.         ST[pos] = 1 << (inp[low] - 'a') ;
  15.         return;
  16.     }
  17.  
  18.     int mid = (low + high) / 2  ;
  19.     build(low, mid, 2*pos+1)    ;
  20.     build(mid+1, high, 2*pos+2) ;
  21.  
  22.     ST[pos] = ST[2*pos+1]^ST[2*pos+2];
  23.  
  24. }
  25.  
  26. inline void update(int idx, int low, int high, int pos, char value){
  27.  
  28.     if(idx < low || idx > high)
  29.         return ;
  30.     if(low == high){
  31.  
  32.         ST[pos] = 1 << (value - 'a')    ;
  33.         return ;
  34.  
  35.     }
  36.  
  37.     int mid = (low + high) / 2                  ;
  38.     update(idx, low, mid, 2*pos+1, value)       ;
  39.     update(idx, mid+1, high, 2*pos+2, value)    ;
  40.     ST[pos] = ST[2*pos+1] ^ ST[2*pos+2]         ;
  41.  
  42. }
  43.  
  44. inline int query(int i, int j, int low, int high, int pos){
  45.  
  46.     if(j < low || i > high)
  47.         return 0    ;
  48.  
  49.     if(i <= low && high <= j)
  50.         return ST[pos]  ;
  51.  
  52.     int mid = (low + high) / 2  ;
  53.  
  54.     return (query(i, j, low, mid, 2*pos+1) ^ query(i, j, mid+1, high, 2*pos+2) )   ;
  55. }
  56.  
  57. int main(){
  58.  
  59.     cin.sync_with_stdio(false)  ;
  60.     cin >> N >> inp   ;
  61.  
  62.     build(0, N-1, 0)    ;
  63.  
  64.     cin >> Q;
  65.  
  66.     for(int i = 0; i < Q; i++){
  67.         cin >> type ;
  68.         if(type == 1){
  69.             int x;
  70.             char k;
  71.             cin >> x >> k   ;
  72.             update(x-1, 0, N-1, 0, k)    ;
  73.         }
  74.  
  75.         else{
  76.  
  77.             int left, right ;
  78.             cin >> left >> right    ;
  79.             left--; right--;
  80.             int ans = query(left, right, 0, N-1, 0) ;
  81.  
  82.             if(__builtin_popcount(ans) <= 1)
  83.                 cout << "YES\n" ;
  84.             else
  85.                 cout << "NO\n"  ;
  86.         }
  87.     }
  88.     return 0    ;
  89. }
  90.  
Time limit exceeded #stdin #stdout 5s 8237056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p3ak2q
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
public

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!