fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const int maxn = 2e5 + 5;
  4.  
  5. int N, Q, root, cnt;
  6. int A[maxn + 5];
  7. std::vector<std::pair<int, int>> st[maxn + 5];
  8. std::vector<int> ed[maxn + 5];
  9.  
  10. int id[maxn + 5], ans[maxn + 5];
  11.  
  12. std::mt19937 rng(time(0));
  13.  
  14. struct Node {
  15.     int p, l, r, key, val, tag, mn, mx;
  16.     Node() {
  17.         key = 0;
  18.         val = 0;
  19.         mn = 0;
  20.         mx = 0;
  21.         l = 0;
  22.         r = 0;
  23.         p = 0;
  24.         tag = 0;
  25.     }
  26.     Node(int x) {
  27.         key = rng();
  28.         val = x;
  29.         mn = x;
  30.         mx = x;
  31.         l = 0;
  32.         r = 0;
  33.         p = 0;
  34.         tag = 0;
  35.     }
  36. } a[maxn + 5];
  37.  
  38. void push(int x) {
  39.     a[a[x].l].mn += a[x].tag;
  40.     a[a[x].r].mn += a[x].tag;
  41.     a[a[x].l].mx += a[x].tag;
  42.     a[a[x].r].mx += a[x].tag;
  43.     a[a[x].l].val += a[x].tag;
  44.     a[a[x].r].val += a[x].tag;
  45.  
  46.     a[a[x].l].tag += a[x].tag;
  47.     a[a[x].r].tag += a[x].tag;
  48.     a[x].tag = 0;
  49. }
  50.  
  51. void pull(int x) {
  52.     a[x].mn = a[x].val;
  53.     a[x].mx = a[x].val;
  54.     if (a[x].l) {
  55.         a[x].mn = std::min(a[x].mn, a[a[x].l].mn);
  56.         a[x].mx = std::max(a[x].mx, a[a[x].l].mx);
  57.     }
  58.     if (a[x].r) {
  59.         a[x].mn = std::min(a[x].mn, a[a[x].r].mn);
  60.         a[x].mx = std::max(a[x].mx, a[a[x].r].mx);
  61.     }
  62. }
  63.  
  64. void pushall(int x) {
  65.     std::vector<int> vec;
  66.     while (a[x].p) {
  67.         vec.push_back(a[x].p);
  68.         x = a[x].p;
  69.     }
  70.     for (int i = (int)vec.size() - 1; i >= 0; --i) {
  71.         push(vec[i]);
  72.     }
  73. }  
  74.  
  75. void split(int x, int k, int &l, int &r) {
  76.     if (!x) {
  77.         l = 0;
  78.         r = 0;
  79.         return;
  80.     }
  81.  
  82.     push(x);
  83.     if (a[x].val <= k) {
  84.         split(a[x].r, k, a[x].r, r);
  85.         a[r].p = 0;
  86.         a[a[x].r].p = x;
  87.         l = x;
  88.     } else {
  89.         split(a[x].l, k, l, a[x].l);
  90.         a[l].p = 0;
  91.         a[a[x].l].p = x;
  92.         r = x;
  93.     }
  94.  
  95.     pull(x);
  96. }
  97.  
  98. void merge(int &x, int l, int r) {
  99.     push(l), push(r);
  100.     if (!l) {
  101.         x = r;
  102.         return;
  103.     }
  104.     if (!r) {
  105.         x = l;
  106.         return;
  107.     }
  108.  
  109.     if (a[l].key > a[r].key) {
  110.         merge(a[l].r, a[l].r, r);
  111.         a[a[l].r].p = l;
  112.         x = l;
  113.     } else {
  114.         merge(a[r].l, l, a[r].l);
  115.         a[a[r].l].p = r;
  116.         x = r;
  117.     }
  118.  
  119.     pull(x);
  120. }
  121.  
  122. void overlapping_merge(int &x, int l, int r) {
  123.     if (!r) {
  124.         x = l;
  125.         return;
  126.     }
  127.     if (!l) {
  128.         x = r;
  129.         return;
  130.     }
  131.     x = 0;
  132.     if (a[l].mn > a[r].mn) std::swap(l, r);
  133.     while (r) {
  134.         int l1, r1;
  135.         split(l, a[r].mn, l1, r1);
  136.         merge(x, x, l1);
  137.         l = r;
  138.         r = r1;
  139.     }
  140.     merge(x, x, l);
  141. }
  142.  
  143. int main() {
  144.     std::cin >> N;
  145.     for (int i = 1; i <= N; ++i)
  146.         std::cin >> A[i];
  147.  
  148.     std::cin >> Q;
  149.     for (int i = 1; i <= Q; ++i) {
  150.         int l, r, x; std::cin >> l >> r >> x;
  151.         st[l].push_back({i, x});
  152.         ed[r].push_back(i);
  153.     }
  154.  
  155.     for (int i = 1; i <= N; ++i) {
  156.         for (auto [q, x] : st[i]) {
  157.             a[++cnt] = Node(x);
  158.  
  159.             id[q] = cnt;
  160.             int l, r;
  161.             split(root, x, l, r);
  162.             merge(root, l, cnt);
  163.             merge(root, root, r);
  164.         }
  165.  
  166.         int l, r;
  167.         split(root, 0, l, r);
  168.  
  169.  
  170.         a[l].mn += A[i];
  171.         a[l].mx += A[i];
  172.         a[l].val += A[i];
  173.         a[l].tag += A[i];   
  174.  
  175.         a[r].mn -= A[i];
  176.         a[r].mx -= A[i];
  177.         a[r].val -= A[i];
  178.         a[r].tag -= A[i];
  179.  
  180.         overlapping_merge(root, l, r);
  181.         for (int q : ed[i]) {
  182.             pushall(id[q]);
  183.             ans[q] = a[id[q]].val;
  184.         }
  185.     }
  186.  
  187.     for (int i = 1; i <= Q; ++i)
  188.         std::cout << ans[i] << '\n';
  189.  
  190.     return 0;
  191. }
Success #stdin #stdout 0.01s 21220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yOcg14
language:
C++14 (gcc 8.3)
created:
3 days 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!