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