daily pastebin goal
51%
SHARE
TWEET

Untitled

keverman Feb 11th, 2019 (edited) 15 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define l(n) (n * 2)
  4. #define r(n) (n * 2 + 1)
  5.  
  6. std::vector<long long> lazy, tree;
  7. std::vector<int> lazy_max, tree_max;
  8.  
  9. int msb(int i)
  10. {
  11.     i |= (i >>  1);
  12.     i |= (i >>  2);
  13.     i |= (i >>  4);
  14.     i |= (i >>  8);
  15.     i |= (i >> 16);
  16.  
  17.     return i - (i >> 1);
  18. }
  19.  
  20. void build(int size)
  21. {
  22.     lazy.resize(msb(size) * 4, 0);
  23.     tree.resize(msb(size) * 4, 0);
  24.     lazy_max.resize(msb(size) * 4, 0);
  25.     tree_max.resize(msb(size) * 4, 0);
  26. }
  27.  
  28. void propagate(int n)
  29. {
  30.     if(l(n) < lazy.size())
  31.     {
  32.         lazy[l(n)] = lazy[n];
  33.         lazy[r(n)] = lazy[n];
  34.     }
  35.  
  36.     lazy[n] = 0;
  37. }
  38.  
  39. void propagate_max(int n)
  40. {
  41.     if(l(n) < lazy_max.size())
  42.     {
  43.         lazy_max[l(n)] = lazy_max[n];x
  44.         lazy_max[r(n)] = lazy_max[n];
  45.     }
  46.  
  47.     lazy_max[n] = 0;
  48. }
  49.  
  50. void update_range(int node, long long start, long long end, long long l, long long r, long long val)
  51. {
  52.     if(lazy[node] != 0)
  53.     {
  54.         tree[node] = lazy[node] * (end - start + 1);
  55.         propagate(node);
  56.     }
  57.  
  58.     if(start > r || end < l)
  59.         return;
  60.  
  61.     if(start >= l && end <= r)
  62.     {
  63.         tree[node] = val * (end - start + 1);
  64.  
  65.         if(start != end)
  66.         {
  67.             lazy[l(node)] = val;
  68.             lazy[r(node)] = val;
  69.         }
  70.     }
  71.  
  72.     else
  73.     {
  74.         long long mid = (start + end) / 2;
  75.         update_range(l(node), start, mid, l, r, val);
  76.         update_range(r(node), mid + 1, end, l, r, val);
  77.         tree[node] = tree[l(node)] + tree[r(node)];
  78.     }
  79. }
  80.  
  81. void update_range_max(int node, int start, int end, int l, int r, int val)
  82. {
  83.     if(lazy_max[node] != 0)
  84.     {
  85.         tree_max[node] = lazy_max[node];
  86.         propagate_max(node);
  87.     }
  88.  
  89.     if(start > r || end < l)
  90.         return;
  91.  
  92.     if(start >= l && end <= r)
  93.     {
  94.         tree_max[node] = val;
  95.  
  96.         if(start != end)
  97.         {
  98.             lazy_max[l(node)] = val;
  99.             lazy_max[r(node)] = val;
  100.         }
  101.     }
  102.  
  103.     else
  104.     {
  105.         int mid = (start + end) / 2;
  106.  
  107.         update_range_max(l(node), start, mid, l, r, val);
  108.         update_range_max(r(node), mid + 1, end, l, r, val);
  109.         tree_max[node] = std::max(tree_max[l(node)], tree_max[r(node)]);
  110.     }
  111. }
  112.  
  113. long long query_range(int node, long long start, long long end, long long l, long long r)
  114. {
  115.     if(start > r || end < l)
  116.         return 0;
  117.  
  118.     if(lazy[node] != 0)
  119.     {
  120.         tree[node] = lazy[node] * (end - start + 1);
  121.         propagate(node);
  122.     }
  123.  
  124.     if(start >= l && end <= r)
  125.         return tree[node];
  126.  
  127.     long long mid = (start + end) / 2;
  128.     return (query_range(l(node), start, mid, l, r) + query_range(r(node), mid + 1, end, l, r));
  129. }
  130.  
  131. int query_range_max(int node, int start, int end, int l, int r)
  132. {
  133.     if(start > r || end < l)
  134.         return 0;
  135.  
  136.     if(lazy_max[node] != 0)
  137.     {
  138.         tree_max[node] = lazy_max[node];
  139.         propagate_max(node);
  140.     }
  141.  
  142.     if(start >= l && end <= r)
  143.         return tree_max[node];
  144.  
  145.     int mid = (start + end) / 2;
  146.     return std::max(query_range_max(l(node), start, mid, l, r),
  147.                     query_range_max(r(node), mid + 1, end, l, r));
  148. }
  149.  
  150. int main()
  151. {
  152.     int n, q;
  153.     std::cin >> n >> q;
  154.     build(n);
  155.  
  156.     while(q--)
  157.     {
  158.         int type, l, r;
  159.         std::cin >> type >> l >> r;
  160.         l--, r--;
  161.  
  162.         switch(type)
  163.         {
  164.         case 1:
  165.  
  166.             long long val;
  167.             std::cin >> val;
  168.             update_range(1, 0, (tree.size() / 2) - 1, l, r, val);
  169.             update_range_max(1, 0, (tree_max.size() / 2) - 1, l, r, val);
  170.             break;
  171.  
  172.         case 2:
  173.  
  174.             std::cout << query_range_max(1, 0, (tree_max.size() / 2) - 1, l, r) << "\n";
  175.             break;
  176.  
  177.         case 3:
  178.  
  179.             std::cout << query_range(1, 0, (tree.size() / 2) - 1, l, r) << "\n";
  180.             break;
  181.         }
  182.     }
  183. }
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