fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node{
  6.  
  7.     int frequency[27] ;
  8.     char replaced   ;
  9.  
  10. };
  11. int N, Q, odd, type;
  12. string inp ;
  13. node ST[380000] ;
  14. node empty_node ;
  15.  
  16. inline void combine(int pos){
  17.  
  18.     for (int i = 0; i < 27; i++)
  19.         ST[pos].frequency[i] = ST[2*pos+1].frequency[i] + ST[2*pos+2].frequency[i]    ;
  20.  
  21. }
  22.  
  23. inline void build(int low, int high, int pos){
  24.  
  25.     if(low==high){
  26.  
  27.         ST[pos].frequency[inp[low] - 'a'] += 1 ;
  28.         ST[pos].replaced = inp[low] ;
  29.         return;
  30.     }
  31.  
  32.     int mid = (low + high) / 2  ;
  33.     build(low, mid, 2*pos+1)    ;
  34.     build(mid+1, high, 2*pos+2) ;
  35.  
  36.     combine(pos)    ;
  37.  
  38. }
  39.  
  40. inline void update(int idx, int low, int high, int pos, char value){
  41.  
  42.     if(idx < low || idx > high)
  43.         return ;
  44.     if(low == high){
  45.  
  46.         ST[pos].frequency[ST[pos].replaced - 'a'] = 0 ;
  47.         ST[pos].frequency[value - 'a'] = 1   ;
  48.         ST[pos].replaced = value ;
  49.         return ;
  50.  
  51.     }
  52.  
  53.     int mid = (low + high) / 2  ;
  54.     update(idx, low, mid, 2*pos+1, value)   ;
  55.     update(idx, mid+1, high, 2*pos+2, value)    ;
  56.     combine(pos)    ;
  57. }
  58.  
  59. inline node query(int i, int j, int low, int high, int pos){
  60.  
  61.     if(j < low || i > high)
  62.         return empty_node   ;
  63.  
  64.     if(i <= low && high <= j)
  65.         return ST[pos]  ;
  66.  
  67.     int mid = (low + high) / 2  ;
  68.     node left, right, output    ;
  69.  
  70.     left = query(i, j, low, mid, 2*pos+1)   ;
  71.     right = query(i, j, mid+1, high, 2*pos+2)   ;
  72.  
  73.     for(int i = 0; i < 27; i++)
  74.         output.frequency[i] = left.frequency[i] + right.frequency[i]  ;
  75.     return output ;
  76.  
  77. }
  78.  
  79. int main(){
  80.  
  81.     cin.sync_with_stdio(false)  ;
  82.     cin >> N >> inp   ;
  83.  
  84.     build(0, N-1, 0)    ;
  85.  
  86.     cin >> Q;
  87.  
  88.     for(int i = 0; i < Q; i++){
  89.         cin >> type ;
  90.         if(type == 1){
  91.             int x;
  92.             char k;
  93.             cin >> x >> k   ;
  94.             update(x-1, 0, N-1, 0, k)    ;
  95.         }
  96.  
  97.         else{
  98.  
  99.             int left, right ;
  100.             cin >> left >> right    ;
  101.             left--; right--;
  102.             node ans = query(left, right, 0, N-1, 0) ;
  103.             odd = 0 ;
  104.  
  105.             for(int i = 0; i < 27; i++)
  106.                 if(ans.frequency[i] % 2)
  107.                     odd++;
  108.             if(odd <= 1)
  109.                 cout << "YES\n" ;
  110.             else
  111.                 cout << "NO\n"  ;
  112.         }
  113.     }
  114.     return 0    ;
  115. }
  116.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BHp1oq
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!