silentkiler029

Segment Tree - Lazy

Dec 3rd, 2021
650
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.             BISMILLAHIR-RAHMANIR-RAHIM
  3.                     SWExSh4n.t0
  4.                         SUST
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define ll long long
  10. #define debug 01
  11.  
  12. std::vector < ll > tree, lazy;
  13. ll n;
  14.  
  15. void update ( ll node, ll node_low, ll node_high, ll query_low, ll query_high, ll val )
  16. {
  17.     if( lazy[node] > 0 ) {
  18.         tree[node] = lazy[node] * (query_high - query_low + 1);
  19.         lazy[2*node] += lazy[node];
  20.         lazy[2*node+1] += lazy[node];
  21.         lazy[node] = 0;
  22.     }
  23.  
  24.     if( node_low >= query_low && node_high <= query_high ) {
  25.         tree[node] += val * ( node_high - node_low + 1 );
  26.         lazy[2*node] += val;
  27.         lazy[2*node+1] += val;
  28.         return;
  29.     }
  30.     if( node_low > query_high || node_high < query_low ) {
  31.         return;
  32.     }
  33.  
  34.     ll mid = ( node_high + node_low ) / 2;
  35.     update( 2 * node, node_low, mid, query_low, query_high, val );
  36.     update( 2 * node + 1, mid + 1, node_high, query_low, query_high, val );
  37.     if( node_low != node_high ) tree[node] = tree[2*node] + tree[2*node+1];
  38.     return;
  39. }
  40.  
  41. ll getSum ( ll node, ll node_low, ll node_high, ll query_low, ll query_high )
  42. {
  43.     if( lazy[node] > 0 ) {
  44.         tree[node] = lazy[node] * (query_high - query_low + 1);
  45.         lazy[2*node] += lazy[node];
  46.         lazy[2*node+1] += lazy[node];
  47.         lazy[node] = 0;
  48.     }
  49.  
  50.     if( node_low >= query_low && node_high <= query_high ) {
  51.         return tree[node];
  52.     }
  53.     if( node_low > query_high || node_high < query_low ) {
  54.         return 0;
  55.     }
  56.     ll mid = ( node_high + node_low ) / 2;
  57.  
  58.     ll sum = getSum( 2 * node, node_low, mid, query_low, query_high ) + getSum( 2 * node + 1, mid + 1, node_high, query_low, query_high );
  59.     if( node_low != node_high ) {
  60.         tree[node] = sum;
  61.     }
  62.     return tree[node];
  63. }
  64.  
  65. int main()
  66. {
  67.     ios_base::sync_with_stdio(false); cin.tie(NULL);  
  68.     ll t, q;
  69.     t = 1;
  70.     std::cin >> t;
  71.     ll cs = 0;
  72.    
  73.     while( t-- ) {
  74.         std::cin >> n >> q;
  75.         while( __builtin_popcount(n) != 1 ) {
  76.             n++;
  77.         }
  78.         tree.resize( 4 * n );
  79.         lazy.resize( 4 * n );
  80.         std::cout << "Case " << ++cs << ":\n";
  81.         while( q-- ) {
  82.             ll q_type;
  83.             std::cin >> q_type;
  84.             if( q_type == 0 ) {
  85.                 ll q_low, q_high, val;
  86.                 std::cin >> q_low >> q_high >> val;
  87.                 update( 1, 0, n-1, q_low, q_high, val );
  88.  
  89.             }
  90.             else {
  91.                 ll q_low, q_high;
  92.                 std::cin >> q_low >> q_high;
  93.                 std::cout << getSum( 1, 0, n-1, q_low, q_high ) << endl;
  94.             }
  95.         }
  96.  
  97.         tree.clear();
  98.         lazy.clear();
  99.     }
  100.     return 0;
  101. }
  102.  
  103. //  ALHAMDULILLAH
RAW Paste Data