fork download
copy 
  1. // generated at caterpillow.github.io/byot
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. // custom monoid
  9.  
  10. const ll mod = 1e9 + 7;
  11. const ll m = 27;
  12. ll mpow(ll x, ll y) {
  13.     ll res = 1;
  14.     while (y) {
  15.         if (y & 1) res = (res * x) % mod;
  16.         x = (x * x) % mod;
  17.         y >>= 1;
  18.     }
  19.     return res;
  20. }
  21.  
  22. // You can implement your own monoid here for custom operations.
  23. struct Value {
  24.     ll hash, rhash, size;
  25.     Value operator+(const Value& oth) const {
  26.         Value res {};
  27.         res.hash = ((hash * mpow(27, oth.size)) % mod + oth.hash) % mod;
  28.         res.rhash = (rhash + (oth.rhash * mpow(27, size)) % mod) % mod;
  29.         res.size = size + oth.size;
  30.         return res;
  31.     }
  32. };
  33.  
  34. const Value vid = {0, 0, 0};
  35.  
  36. // end custom code
  37.  
  38. mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  39. using ptr = struct Node*;
  40.  
  41. struct Node {
  42.     Value val;
  43.     Value agg;
  44.  
  45.     int sz;
  46.     int pri;
  47.     ptr l, r;
  48.  
  49.     Node() {
  50.         pri = mt();
  51.         val = vid;
  52.         agg = vid;
  53.         sz = 1;
  54.         l = r = nullptr;
  55.     }
  56.  
  57.     Node(Value val) : val(val), agg(val) {
  58.         pri = mt();
  59.         sz = 1;
  60.         l = r = nullptr;
  61.     }
  62.  
  63.     ~Node() {
  64.         delete l;
  65.         delete r;
  66.     }
  67. };
  68.  
  69. int sz(ptr n) { return n ? n->sz : 0; };
  70. Value agg(ptr n) { return n ? n->agg : vid; }
  71.  
  72. ptr pull(ptr n) {
  73.     if (!n) return nullptr;
  74.     n->sz = sz(n->l) + 1 + sz(n->r);
  75.     n->agg = agg(n->l) + n->val + agg(n->r);
  76.     return n;
  77. }
  78.  
  79. ptr merge(ptr l, ptr r) {
  80.     if (!l || !r) return l ? l : r;
  81.     if (l->pri > r->pri) return l->r = merge(l->r, r), pull(l);
  82.     else return r->l = merge(l, r->l), pull(r);
  83. }
  84.  
  85. // [-inf, i) and [i, inf]
  86. pair<ptr, ptr> spliti(ptr n, int i) {
  87.     if (!n) return {nullptr, nullptr};
  88.     if (i <= sz(n->l)) {
  89.         auto [l, r] = spliti(n->l, i);
  90.         n->l = r;
  91.         return {l, pull(n)};
  92.     } else {
  93.         auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
  94.         n->r = l;
  95.         return {pull(n), r};
  96.     }
  97. }
  98.  
  99. // cuts out [lo, hi)
  100. tuple<ptr, ptr, ptr> spliti(ptr n, int lo, int hi) {
  101.     auto [lm, r] = spliti(n, hi);
  102.     auto [l, m] = spliti(lm, lo);
  103.     return {l, m, r};
  104. }
  105.  
  106. // inserts node such that it will be at index i. only insert single nodes
  107. void insi(ptr& n, ptr it, int i) {
  108.     if (!n) { n = it; return; }
  109.     if (n->pri < it->pri) {
  110.         auto [l, r] = spliti(n, i);
  111.         it->l = l, it->r = r, n = it;
  112.     } else if (i <= sz(n->l)) insi(n->l, it, i);
  113.     else insi(n->r, it, i - 1 - sz(n->l));
  114.     pull(n);
  115. }
  116.  
  117. Value queryi(ptr n, int lo, int hi) {
  118.     if (!n || lo >= sz(n) || hi <= 0) return vid;
  119.     if (lo <= 0 && sz(n) <= hi) return n->agg;
  120.     return queryi(n->l, lo, hi) + (lo <= sz(n->l) && sz(n->l) < hi ? n->val : vid) + queryi(n->r, lo - 1 - sz(n->l), hi - 1 - sz(n->l));
  121. }
  122.  
  123. void heapify(ptr n) {
  124.     if (!n) return;
  125.     ptr mx = n;
  126.     if (n->l && n->l->pri > mx->pri) mx = n->l;
  127.     if (n->r && n->r->pri > mx->pri) mx = n->r;
  128.     if (mx != n) swap(n->pri, mx->pri), heapify(mx);
  129. }
  130.  
  131. ptr build(vector<ptr>& ns, int l = 0, int r = -69) {
  132.     if (r == -69) r = (int) ns.size() - 1;
  133.     if (l > r) return nullptr;
  134.     if (l == r) return ns[l];
  135.     int m = (l + r) / 2;
  136.     ns[m]->l = build(ns, l, m - 1);
  137.     ns[m]->r = build(ns, m + 1, r);
  138.     heapify(ns[m]);
  139.     return pull(ns[m]);
  140. }
  141.  
  142. /*
  143.  
  144. - include merge
  145. - include 3-way split by index (and size, and split by index)
  146. - include point insert by index 
  147. - include build (and heapify)
  148. - include range queries (and range aggregates)
  149.  
  150. */
  151.  
  152. main() {
  153.     cin.tie(0)->sync_with_stdio(0);
  154.  
  155.     int n, q; cin >> n >> q;
  156.     string st; cin >> st;
  157.  
  158.     vector<ptr> ns(n);
  159.     for (int i = 0; i < n; i++) {
  160.         ns[i] = new Node({st[i] - 'a' + 1, st[i] - 'a' + 1, 1});
  161.     }
  162.     ptr treap = build(ns);
  163.  
  164.     while (q--) {
  165.         int t; cin >> t;
  166.         if (t == 1) {
  167.             int lo, hi; cin >> lo >> hi;
  168.             auto [l, m, r] = spliti(treap, lo - 1, hi);
  169.             treap = merge(l, r);
  170.             delete m;
  171.         }
  172.         if (t == 2) {
  173.             char c;
  174.             int p;
  175.             cin >> c >> p;
  176.             insi(treap, new Node {{c - 'a' + 1, c - 'a' + 1, 1}}, p - 1);
  177.         }
  178.         if (t == 3) {
  179.             int l, r; cin >> l >> r;
  180.             Value res = queryi(treap, l - 1, r);
  181.             cout << (res.hash == res.rhash ? "yes" : "no") << '\n';
  182.         }
  183.     }
  184.     delete treap;
  185. }
  186.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
4 4
aaaa
1 3 4
3 1 1
3 1 1
2 a 3
stdout
copy 
yes
yes
https://ideone.com/n9rTat
yes
yes

language:
C++14 (gcc 8.3)
created:
16 hours 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!