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