fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define endl '\n'
  5. #define all(n) (n).begin(), (n).end()
  6. using namespace std;
  7.  
  8. const ll oo = 1e18;
  9. const ll mod = 1e9 + 7;
  10. const ll nmax = 2e5 + 8;
  11. const ll base = 31;
  12.  
  13. ll n, q, POW[nmax];
  14. void create(){
  15.     POW[0] = 1;
  16.     for ( ll i = 1; i <= 1e5; ++i){
  17.         POW[i] = (POW[i - 1] * base) % mod;
  18.     }
  19. }
  20. struct IT{
  21.     ll st[4 * nmax];
  22.     string s;
  23.     void build( ll i, ll l, ll r){
  24.         if ( l == r){
  25.             st[i] = s[l - 1] - 'a' + 1;
  26.             return;
  27.         }
  28.         ll mid = ( l + r ) / 2;
  29.         build(2 * i, l, mid);
  30.         build(2 * i + 1, mid + 1, r);
  31.         st[i] = ((st[2 * i] * POW[r - mid]) % mod + st[2 * i + 1]) % mod;
  32.     }
  33.     void update( ll i, ll l, ll r, ll pos, char val){
  34.         if ( pos < l || pos > r){
  35.             return;
  36.         }
  37.         if ( l == r){
  38.             st[i] = val - 'a' + 1;
  39.             return;
  40.         }
  41.         ll mid = ( l + r ) / 2;
  42.         update(2 * i, l, mid, pos, val);
  43.         update(2 * i + 1, mid + 1, r, pos, val);
  44.         st[i] = ((st[2 * i] * POW[r - mid]) % mod + st[2 * i + 1]) % mod;
  45.     }
  46.     ll get(ll i, ll l, ll r, ll u, ll v){
  47.         if ( v < l || u > r || u > v){
  48.             return 0;
  49.         }
  50.         if ( u <= l && r <= v){
  51.             return st[i];
  52.         }
  53.         ll mid = (l + r) / 2;
  54.         return (get(i * 2, l, mid, u, v) * POW[max(0LL, min(r, v) - mid)] % mod + get(i * 2 + 1, mid + 1, r, u, v)) % mod;
  55.     }
  56. };
  57. IT res, sol;
  58. main(){
  59.     fast;
  60.     create();
  61.     cin >> n >> q >> res.s;
  62.     sol.s = res.s;
  63.     sol.s = sol.s;
  64.     reverse(all(res.s));
  65.     res.s = res.s;
  66.     res.build(1, 1, n); sol.build(1, 1, n);
  67.     while(q--){
  68.         ll type;
  69.         cin >> type;
  70.         if ( type == 1){
  71.             ll pos; char x;
  72.             cin >> pos >> x;
  73.             sol.update(1, 1, n, pos, x);
  74.             res.update(1, 1, n, n - pos + 1, x);
  75.         }
  76.         else{
  77.             ll x, y;
  78.             cin >> x >> y;
  79.             ll j = sol.get(1, 1, n, x, y);
  80.             ll k = res.get(1, 1, n, n - y + 1, n - x + 1);
  81.             if ( j == k ){
  82.                 cout << "YES" << endl;
  83.             }
  84.             else{
  85.                 cout << "NO" << endl;
  86.             }
  87.         }
  88.     }
  89. }
  90.  
Runtime error #stdin #stdout 1.53s 2096112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ug3iG3
language:
C++14 (gcc 8.3)
created:
333 days 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!