fork download 
  1. //      ﷽
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7. struct Node {
  8.     Node *left{}, *right{};
  9.     int sum{};
  10.     int lazy{}; 
  11.  
  12.     Node() {}
  13.     Node(int val) : sum(val), lazy(0) {}
  14.  
  15.     Node(Node* other) {
  16.         if (other) {
  17.             left = other->left;
  18.             right = other->right;
  19.             sum = other->sum;
  20.             lazy = other->lazy;
  21.         }
  22.     }
  23.  
  24.     Node(Node *l, Node *r) {
  25.         left = l;
  26.         right = r;
  27.         sum = 0;
  28.         lazy = 0;
  29.         if (left) sum += left->sum;
  30.         if (right) sum += right->sum;
  31.     } 
  32. };
  33.  
  34. struct PST {
  35.     int n;
  36.     vector<Node*> roots;
  37.  
  38.     PST(int n, int m) : n(n), roots(m) { }
  39.  
  40.     Node* build(int l, int r, vector<int>& a) {
  41.         if (l == r) return new Node(a[l]);
  42.         int mid = (l + r) / 2;
  43.         Node* left = build(l, mid, a);
  44.         Node* right = build(mid + 1, r, a);
  45.         return new Node(left, right);
  46.     } 
  47.  
  48.     Node merge(Node l, Node r) {
  49.         Node ret;
  50.         ret.sum = l.sum + r.sum;
  51.         return ret;
  52.     }
  53.  
  54.     Node* update(Node* node, int l, int r, int ql, int qr, int val) {
  55.         Node* curr = new Node(node);
  56.  
  57.         int overlap = max(0LL, min(r, qr) - max(l, ql) + 1);
  58.         curr->sum += val * overlap;
  59.  
  60.         if (ql <= l && r <= qr) {
  61.             curr->lazy += val;
  62.             return curr;
  63.         }
  64.  
  65.         int mid = (l + r) / 2;
  66.         if (ql <= mid) curr->left = update(curr->left, l, mid, ql, qr, val);
  67.         if (qr > mid)  curr->right = update(curr->right, mid + 1, r, ql, qr, val);
  68.  
  69.         return curr;
  70.     }
  71.  
  72.     Node* update(int v, int ql, int qr, int val) { return update(roots[v], 0, n - 1, ql, qr, val); }
  73.  
  74.     Node query(Node* node, int l, int r, int ql, int qr, int add) {
  75.         if (!node || l > qr || r < ql) return {};
  76.  
  77.         if (l >= ql && r <= qr) { return node->sum + add * (r - l + 1); }
  78.  
  79.         int mid = (l + r) / 2;
  80.         int next_add = add + node->lazy; 
  81.  
  82.         return merge(query(node->left, l, mid, ql, qr, next_add), 
  83.                query(node->right, mid + 1, r, ql, qr, next_add));
  84.     } 
  85.  
  86.     int query(int v, int l, int r) { 
  87.         return query(roots[v], 0, n - 1, l, r, 0).sum; 
  88.     }
  89. };
  90.  
  91. void solve(int testcase) {
  92.     int n, q; cin >> n >> q;
  93.     vector<int> arr(n);
  94.     for (auto& i : arr) cin >> i;
  95.     PST pst(n, q + 1);
  96.     pst.roots[0] = pst.build(0, n - 1, arr);
  97.     int t = 0;
  98.     while (q--) {
  99.         char op; cin >> op;
  100.         if (op == 'C') {
  101.             int l, r, d; cin >> l >> r >> d; --l, --r;
  102.             // the bug is here 
  103.             pst.roots[++t] = pst.update(t, l, r, d);
  104.         } else if (op == 'Q') {
  105.             int l, r; cin >> l >> r; --l, --r;
  106.             cout << pst.query(t, l, r) << '\n';
  107.         } else if (op == 'H') {
  108.             int to, l, r; cin >> l >> r >> to; --l, --r;
  109.             cout << pst.query(to, l, r) << '\n';
  110.         } else {
  111.             int to; cin >> to;
  112.             t = to;
  113.         }
  114.     }
  115. }
  116.  
  117. signed main() {
  118.     ios::sync_with_stdio(false);
  119.     cin.tie(nullptr);
  120.  
  121.     //freopen("input.txt", "r", stdin);
  122.     //freopen("output.txt", "w", stdout);
  123.  
  124.     int T = 1;
  125.     // cin >> T;
  126.     for (int _ = 1; _ <= T; ++_) 
  127.         solve(_);
  128.  
  129.     return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0.04s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/uXMeOB
language:
C++14 (gcc 8.3)
created:
13 hours ago
visibility:
secret

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!