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