ulvis.paste.net

Paste Search Dynamic
Recent pastes
getans
  1. #include <bits/stdc++.h>
  2. #define LEFT(n) (n<<1)
  3. #define RIGHT(n) (n<<1|1)
  4. using namespace std;
  5.  
  6. int N, Q;
  7. long long tree[1200005], lazy[1200005];
  8.  
  9. void update(int node, int low, int up, int l, int r, long long value){
  10.   if(lazy[node]){
  11.         tree[node] += (up - low + 1)* lazy[node];
  12.         if(up != low){
  13.                 lazy[LEFT(node)] += lazy[node];
  14.                 lazy[RIGHT(node)] += lazy[node];
  15.         }
  16.         lazy[node] = 0;
  17.   }
  18.   if(up < l || low > r || low > up)
  19.     return;
  20.  
  21.   if(l <= low && up <=r){
  22.     tree[node] += (up - low + 1) * value;
  23.     if(up != low){
  24.         lazy[LEFT(node)] += value;
  25.         lazy[RIGHT(node)] += value;
  26.     }
  27.     return;
  28.   }
  29.   int mid = (low + up) >> 1;
  30.   update(LEFT(node), low, mid, l, r, value);
  31.   update(RIGHT(node), mid + 1, up, l, r, value);
  32.   tree[node] = tree[LEFT(node)] + tree[RIGHT(node)];
  33. }
  34.  
  35. long long getans(int node, int low, int up, int l, int r){
  36.   if(lazy[node]){
  37.         tree[node] += lazy[node] * (up - low + 1);
  38.         if(up != low){
  39.                 lazy[LEFT(node)] += lazy[node];
  40.                 lazy[RIGHT(node)] += lazy[node];
  41.         }
  42.         lazy[node] = 0;
  43.   }
  44.   if(up < l || low > r || low > up)
  45.     return 0;
  46.  
  47.   if(l <= low && up <= r){
  48.     return tree[node];
  49.   }
  50.   int mid = (up + low) >> 1;
  51.   long long temp = getans(LEFT(node), low, mid, l, r);
  52.   temp += getans(RIGHT(node), mid + 1, up, l, r);
  53.   return temp;
  54. }
  55.  
  56. int main() {
  57.   ios_base::sync_with_stdio(false);
  58.   int tc;
  59.   cin >> tc;
  60.   while(tc--){
  61.         memset(tree, 0, sizeof(tree));
  62.         memset(lazy, 0, sizeof(lazy));
  63.     cin >> N >> Q;
  64.     while(Q--){
  65.       bool type;int r1, r2;long long inc;
  66.       cin >> type >> r1 >> r2;
  67.       if(!type){
  68.         cin >> inc;
  69.         update(1, 1, N, r1, r2, inc);
  70.       }else{
  71.         cout << getans(1, 1, N, r1, r2) << "\n";
  72.       }
  73.     }
  74.   }
  75. }
Parsed in 0.014 seconds