SHARE
TWEET

Untitled

a guest Jan 24th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma comment(linker, "/stack:200000000"]
  2. #pragma GCC optimize("Ofast"]
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native"]
  4. #include<iostream>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<unordered_set>
  10. #include<unordered_map>
  11. #include<map>
  12. #include<algorithm>
  13. #include<queue>
  14. #include<stack>
  15. #include<cstdio>
  16. #include<random>
  17. #include<cassert>
  18. #include<sstream>
  19. #include<set>
  20.  
  21. using namespace std;
  22.  
  23. const int maxN = 1e5 + 10;
  24. const int base = 255;
  25. const int mod = 1791791791;
  26.  
  27. int n, q;
  28. string s;
  29. int pows[maxN];
  30. int pref[maxN];
  31.  
  32. void init(){
  33.     pows[0] = 1;
  34.     pref[0] = 1;
  35.     for(int i = 1; i < maxN; i++){
  36.         pows[i] = (1ll * pows[i - 1] * base) % mod;
  37.         pref[i] = (1ll * pref[i - 1] + pows[i]) % mod;
  38.     }
  39. }
  40.  
  41. struct node{
  42.     int add, sz;
  43.     pair<int, int> h;
  44.     node(int h = 0, int sz = 0, int add = -1){
  45.         this->h = {h, h};
  46.         this->add = add;
  47.         this->sz = sz;
  48.     }
  49.     pair<int, int> getHash(){
  50.         if(add > -1){
  51.             int pans = (1ll * add * pref[sz - 1]) % mod;
  52.             return {pans, pans};
  53.         }else return h;
  54.     }
  55. };
  56.  
  57. struct segmentTree{
  58.     node t[4 * maxN];
  59.     segmentTree(){
  60.         build();
  61.     }
  62.     void push(int v){
  63.         if(t[v].add == -1)return;
  64.         t[2 * v + 1].add = t[v].add;
  65.         t[2 * v + 2].add = t[v].add;
  66.         t[v].add = -1;
  67.     }
  68.     void merge(int v, int tl, int tr){
  69.         int mid = (tl + tr) / 2;
  70.         int szR = tr - mid, szL = mid - tl;
  71.         t[v].h.first = ((1ll * t[2 * v + 1].getHash().first * pows[szR]) % mod + t[2 * v + 2].getHash().first) % mod;
  72.         t[v].h.second = ((1ll * t[2 * v + 2].getHash().second * pows[szL]) % mod + t[2 * v + 1].getHash().second) % mod;
  73.     }
  74.     void build(int v = 0, int tl = 0, int tr = n){
  75.         if(tr - tl == 1)t[v] = node(s[tl], 1, -1);
  76.         else{
  77.             int mid = (tl + tr) / 2;
  78.             build(2 * v + 1, tl, mid);
  79.             build(2 * v + 2, mid, tr);
  80.             t[v].sz = tr - tl;
  81.             merge(v, tl, tr);
  82.         }
  83.     }
  84.     void change(int L, int R, int x, int v = 0, int tl = 0, int tr = n){
  85.         if(R <= tl || L >= tr || tr - tl < 1)return;
  86.         else if(L <= tl && tr <= R)t[v].add = x;
  87.         else{
  88.             push(v);
  89.             int mid = (tl + tr) / 2;
  90.             change(L, R, x, 2 * v + 1, tl, mid);
  91.             change(L, R, x, 2 * v + 2, mid, tr);
  92.             merge(v, tl, tr);
  93.         }
  94.     }
  95.     node get(int L, int R, int v = 0, int tl = 0, int tr = n){
  96.         if(L <= tl && tr <= R)return t[v];
  97.         else{
  98.             push(v);
  99.             int mid = (tl + tr) / 2;
  100.             node ans;
  101.             if(L >= mid)ans = get(L, R, 2 * v + 2, mid, tr);
  102.             else if(R <= mid)ans = get(L, R, 2 * v + 1, tl, mid);
  103.             else{
  104.                 node l = get(L, R, 2 * v + 1, tl, mid);
  105.                 node r = get(L, R, 2 * v + 2, mid, tr);
  106.                 ans.h.first = ((1ll * l.getHash().first * pows[r.sz]) % mod + r.getHash().first) % mod;
  107.                 ans.h.second = ((1ll * r.getHash().second * pows[l.sz]) % mod + l.getHash().second) % mod;
  108.                 ans.sz = l.sz + r.sz;
  109.             }
  110.             merge(v, tl, tr);
  111.             return ans;
  112.         }
  113.     }
  114. };
  115.  
  116. signed main(){
  117.     ios_base::sync_with_stdio(0);
  118.     cin.tie(0);
  119.     cout.tie(0);
  120.     init();
  121.     cin >> n >> q;
  122.     cin >> s;
  123.     segmentTree t;
  124.     for(int i = 0; i < q; i++){
  125.         string s; cin >> s;
  126.         if(s[0] == 'a'){
  127.             int l, r; cin >> l >> r; l--;
  128.             node ans = t.get(l, r);
  129.             if(ans.getHash().first == ans.getHash().second)cout << "YES\n";
  130.             else cout << "NO\n";
  131.         }else{
  132.             int l, r; char c; cin >> l >> r >> c; l--;
  133.             t.change(l, r, c);
  134.         }
  135.     }
  136.     return 0;
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top