fork download 
  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. struct Lazy {
  9.     // set, then reverse, then flip
  10.     int set;
  11.     bool rev;
  12.     bool flip;
  13.  
  14.     void operator+=(const Lazy& oth) {
  15.         if (oth.set != -1) rev = flip = 0, set = oth.set;
  16.         rev ^= oth.rev;
  17.         flip ^= oth.flip;
  18.     }
  19. };
  20.  
  21. const Lazy lid = {-1, false, false};
  22.  
  23. // You can implement your own monoid here for custom operations.
  24. struct Value {
  25.     int ans, tot0, tot1, pfx0, pfx1, sfx0, sfx1;
  26.  
  27.     static Value make(int x, int len = 1) {
  28.         if (x) return {len, 0, len, 0, len, 0, len};
  29.         else return {len, len, 0, len, 0, len, 0};
  30.     } 
  31.  
  32.     void upd(Lazy lazy, int sz) {
  33.         if (lazy.set != -1) {
  34.             *this = make(lazy.set, tot0 + tot1);
  35.         }
  36.         if (lazy.rev) {
  37.             swap(pfx0, sfx0);
  38.             swap(pfx1, sfx1);
  39.         }
  40.         if (lazy.flip) {
  41.             swap(tot0, tot1);
  42.             swap(pfx0, pfx1);
  43.             swap(sfx0, sfx1);
  44.         }
  45.     }
  46.  
  47.     Value operator+(const Value& oth) const {
  48.         Value res {};
  49.         res.ans = max({ans, oth.ans, sfx0 + oth.pfx0, sfx1 + oth.pfx1});
  50.         res.tot0 = tot0 + oth.tot0;
  51.         res.tot1 = tot1 + oth.tot1;
  52.         if (tot1 == 0) res.pfx0 = tot0 + oth.pfx0;
  53.         else res.pfx0 = pfx0;
  54.         if (tot0 == 0) res.pfx1 = tot1 + oth.pfx1;
  55.         else res.pfx1 = pfx1;
  56.         if (oth.tot1 == 0) res.sfx0 = sfx0 + oth.tot0;
  57.         else res.sfx0 = oth.sfx0;
  58.         if (oth.tot0 == 0) res.sfx1 = sfx1 + oth.tot1;
  59.         else res.sfx1 = oth.sfx1;
  60.         return res;
  61.     }
  62. };
  63.  
  64. const Value vid = {0, 0, 0, 0, 0, 0, 0};
  65.  
  66. // end custom code
  67.  
  68. // generated at caterpillow.github.io/byot
  69.  
  70. mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  71. using ptr = struct Node*;
  72.  
  73. struct Node {
  74.     Value val;
  75.     Value agg;
  76.     Lazy lazy;
  77.  
  78.     int sz;
  79.     int pri;
  80.     ptr l, r;
  81.  
  82.     Node() {
  83.         pri = mt();
  84.         val = vid;
  85.         agg = vid;
  86.         lazy = lid;
  87.         sz = 1;
  88.         l = r = nullptr;
  89.     }
  90.  
  91.     Node(Value val) : val(val), agg(val) {
  92.         pri = mt();
  93.         lazy = lid;
  94.         sz = 1;
  95.         l = r = nullptr;
  96.     }
  97.  
  98.     ~Node() {
  99.         delete l;
  100.         delete r;
  101.     }
  102. };
  103.  
  104. int sz(ptr n) { return n ? n->sz : 0; };
  105. Value agg(ptr n) { return n ? n->agg : vid; }
  106.  
  107. void push(ptr n) {
  108.     n->val.upd(n->lazy, 1);
  109.     n->agg.upd(n->lazy, sz(n));
  110.     if (n->lazy.rev) swap(n->l, n->r);
  111.     if (n->l) n->l->lazy += n->lazy;
  112.     if (n->r) n->r->lazy += n->lazy;
  113.     n->lazy = lid;
  114. }
  115.  
  116. ptr pull(ptr n) {
  117.     if (!n) return nullptr;
  118.     if (n->l) push(n->l);
  119.     if (n->r) push(n->r);
  120.     n->sz = sz(n->l) + 1 + sz(n->r);
  121.     n->agg = agg(n->l) + n->val + agg(n->r);
  122.     return n;
  123. }
  124.  
  125. ptr merge(ptr l, ptr r) {
  126.     if (!l || !r) return l ? l : r;
  127.     push(l), push(r);
  128.     if (l->pri > r->pri) return l->r = merge(l->r, r), pull(l);
  129.     else return r->l = merge(l, r->l), pull(r);
  130. }
  131.  
  132. // [-inf, i) and [i, inf]
  133. pair<ptr, ptr> spliti(ptr n, int i) {
  134.     if (!n) return {nullptr, nullptr};
  135.     push(n);
  136.     if (i <= sz(n->l)) {
  137.         auto [l, r] = spliti(n->l, i);
  138.         n->l = r;
  139.         return {l, pull(n)};
  140.     } else {
  141.         auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
  142.         n->r = l;
  143.         return {pull(n), r};
  144.     }
  145. }
  146.  
  147. // you CANNOT use the normal range update for range reverses
  148. void reversei(ptr& n, int lo, int hi) {
  149.     auto [lm, r] = spliti(n, hi);
  150.     auto [l, m] = spliti(lm, lo);
  151.     Lazy upd = lid;
  152.     upd.rev = true;
  153.     if (m) m->lazy += upd;
  154.     n = merge(merge(l, m), r);
  155. }
  156.  
  157. void updi(ptr n, int lo, int hi, Lazy lazy) {
  158.     if (!n) return;
  159.     push(n);
  160.     if (lo >= n->sz || hi <= 0) return;
  161.     if (lo <= 0 && n->sz <= hi) {
  162.         n->lazy += lazy;
  163.         push(n);
  164.         return;
  165.     }
  166.     if (lo <= sz(n->l) && sz(n->l) < hi) n->val.upd(lazy, 1);
  167.     updi(n->l, lo, hi, lazy);
  168.     updi(n->r, lo - 1 - sz(n->l), hi - 1 - sz(n->l), lazy);
  169.     pull(n);
  170. }
  171.  
  172. Value queryi(ptr n, int lo, int hi) {
  173.     if (!n || lo >= sz(n) || hi <= 0) return vid;
  174.     push(n);
  175.     if (lo <= 0 && sz(n) <= hi) return n->agg;
  176.     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));
  177. }
  178.  
  179. void heapify(ptr n) {
  180.     if (!n) return;
  181.     ptr mx = n;
  182.     if (n->l && n->l->pri > mx->pri) mx = n->l;
  183.     if (n->r && n->r->pri > mx->pri) mx = n->r;
  184.     if (mx != n) swap(n->pri, mx->pri), heapify(mx);
  185. }
  186.  
  187. ptr build(vector<ptr>& ns, int l = 0, int r = -69) {
  188.     if (r == -69) r = (int) ns.size() - 1;
  189.     if (l > r) return nullptr;
  190.     if (l == r) return ns[l];
  191.     int m = (l + r) / 2;
  192.     ns[m]->l = build(ns, l, m - 1);
  193.     ns[m]->r = build(ns, m + 1, r);
  194.     heapify(ns[m]);
  195.     return pull(ns[m]);
  196. }
  197.  
  198. /*
  199.  
  200. - include range reverse by index (and lazy prop, size, split by index and merge)
  201. - include build (and heapify)
  202. - include range aggregates
  203. - include range updates by index
  204. - include range queries by index
  205.  
  206. */
  207.  
  208. main() {
  209.     cin.tie(0)->sync_with_stdio(0);
  210.  
  211.     int n, q; cin >> n >> q;
  212.  
  213.     vector<ptr> ns(n);
  214.     for (int i = 0; i < n; i++) {
  215.         char x; cin >> x;
  216.         ns[i] = new Node(Value::make(x - '0'));
  217.     }
  218.     ptr treap = build(ns);
  219.  
  220.     for (int i = 0; i < q; i++) {
  221.         int t, l, r; cin >> t >> l >> r;
  222.         l--;
  223.         if (t == 1) {
  224.             updi(treap, l, r, {-1, false, true});
  225.         }
  226.         if (t == 2) {
  227.             reversei(treap, l, r);
  228.         }
  229.         if (t == 3) {
  230.             Value res = queryi(treap, l, r);
  231.             updi(treap, l, l + res.tot0, {0, false, false});
  232.             updi(treap, r - res.tot1, r, {1, false, false});
  233.         }
  234.         push(treap); 
  235.         cout << agg(treap).ans << '\n';
  236.     }
  237.     delete treap;
  238. }
  239.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
8 8
00000000
1 1 3
2 2 7
2 2 4
2 5 6
2 5 5
3 1 8
1 4 5
3 6 8
stdout 
5
4
4
3
3
5
5
5
https://ideone.com/OdZCxS
5
4
4
3
3
5
5
5
language:
C++14 (gcc 8.3)
created:
1 day 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!