fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. struct node{
  6.     map<int, int> cnt;
  7.     int delta, prom, lv, rv;
  8.     node *left, *right;
  9.     node() : left(NULL), right(NULL), delta(0), prom(0) {}
  10.  
  11.     void update(node *a, node *b) {
  12.         cnt.clear();
  13.         delta = 0;
  14.  
  15.         for (pair<int, int> i : a->cnt) {
  16.             cnt[i.first + a->delta] = i.second;
  17.         }
  18.         for (pair<int, int> i : b->cnt) {
  19.             cnt[i.first + b->delta] += i.second;
  20.         }
  21.     }
  22.  
  23.     void push() {
  24.         left->delta += prom;
  25.         right->delta += prom;
  26.         left->prom += prom;
  27.         right->prom += prom;
  28.         prom = 0;
  29.         /// prom - promise
  30.     }
  31.  
  32.     int get(int l, int r, int x) {
  33.         if (l > rv || lv > r) {
  34.             return 0;
  35.         }
  36.         if (l <= lv && rv <= r) {
  37.             return cnt.find(x - delta) != cnt.end() ? cnt[x - delta] : 0;
  38.             /// here we can just write return cnt[x-delta], but it will create empty cell
  39.         }
  40.         push();
  41.         return left->get(l, r, x) + right->get(l, r, x);
  42.     }
  43.  
  44.     void inc(int l, int r, int toInc) {
  45.         if (l > rv || lv > r) {
  46.             return;
  47.         }
  48.         if (l <= lv && rv <= r) {
  49.             delta += toInc;
  50.             prom += toInc;
  51.             return;
  52.         }
  53.         left->inc(l, r, toInc);
  54.         right->inc(l, r, toInc);
  55.         update(left, right);
  56.     }
  57. };
  58.  
  59.  
  60. main() {
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0s 3292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cLGBfK
language:
C++14 (gcc 8.3)
created:
9 years 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!