SHARE
TWEET

STI

Manioc Jun 26th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define MAX 100007
  3.  
  4. using namespace std;
  5.  
  6. struct node{
  7.     int val, acum;
  8.     node *l, *r;
  9.  
  10.     node(){
  11.         val = acum = 0;
  12.         l = r = NULL;
  13.     }
  14. } *root;
  15.  
  16. void add(node* no,int l, int r, int v){
  17.     no->val += (r-l+1)*v;
  18.     no->acum += v;
  19. }
  20.  
  21. void update(node* no, int l, int r, int x, int y, int v){
  22.     if(r < x || y < l) return;
  23.     else if(x <= l && r <= y) add(no, l, r,  v);
  24.     else{
  25.         int mid = (l+r)/2;
  26.  
  27.         no->l = (no->l == NULL)? new node(): no->l;
  28.         no->r = (no->r == NULL)? new node(): no->r;
  29.         add(no->l, l, mid, no->acum);
  30.         add(no->r, mid+1, r,no->acum);
  31.         no->acum = 0;
  32.  
  33.         update(no->l, l, mid, x, y, v);
  34.         update(no->r, mid+1, r, x, y, v);
  35.  
  36.         no->val = no->l->val + no->r->val;
  37.     }
  38. }
  39.  
  40. int query(node* no, int l, int r, int x, int y){
  41.     if(r < x || y < l) return 0;
  42.     else if(x <= l && r <= y) return no->val;
  43.     else{
  44.         int mid = (l+r)/2;
  45.  
  46.         no->l = (no->l == NULL)? new node(): no->l;
  47.         no->r = (no->r == NULL)? new node(): no->r;
  48.         add(no->l, l, mid, no->acum);
  49.         add(no->r, mid+1, r,no->acum);
  50.         no->acum = 0;
  51.  
  52.         return query(no->l, l, mid, x, y) +
  53.                query(no->r, mid+1, r, x, y);
  54.  
  55.     }
  56. }
  57. int main(){
  58.     return 0;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top