SHARE
TWEET

Untitled

a guest Jan 15th, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5.  
  6. using std::cin;
  7. using std::cout;
  8. using std::max;
  9. using std::min;
  10. using std::pair;
  11. using std::vector;
  12.  
  13. vector<int> Mas;
  14. vector<int> Add_Mas;
  15.  
  16. void push(int vert, int vl_bnd, int vr_bnd) {
  17.     if (vl_bnd != vr_bnd) {
  18.         Add_Mas[ 2 * vert + 1 ] += Add_Mas[ vert ];
  19.         Add_Mas[ 2 * vert + 2 ] += Add_Mas[ vert ];
  20.     }
  21.     Mas[ vert ] += Add_Mas[ vert ];
  22.     Add_Mas[ vert ] = 0;
  23. }
  24.  
  25. void build(int vert, int vl_bnd, int vr_bnd, vector<int>& mas_in) {
  26.     if (vl_bnd == vr_bnd) {
  27.         Mas[ vert ] = mas_in[ vl_bnd ];
  28.         return;
  29.     }
  30.     int mid = vl_bnd + (vr_bnd - vl_bnd) / 2;
  31.     build(2 * vert + 1, vl_bnd, mid, mas_in);
  32.     build(2 * vert + 2, mid + 1, vr_bnd, mas_in);
  33.     Mas[ vert ] = max(Mas[ 2 * vert + 1 ], Mas[ 2 * vert + 2 ]);
  34. }
  35.  
  36. int query(int vert, int vl_bnd, int vr_bnd, int left, int right) {
  37.     push(vert, vl_bnd, vr_bnd);
  38.     if (right < vl_bnd || vr_bnd < left)
  39.         return 0;
  40.     if (left <= vl_bnd && vr_bnd <= right)
  41.         return Mas[ vert ];
  42.     int mid = vl_bnd + (vr_bnd - vl_bnd) / 2;
  43.     int query_l = query(2 * vert + 1, vl_bnd, mid, left, right);
  44.     int query_r = query(2 * vert + 2, mid + 1, vr_bnd, left, right);
  45.     return max(query_l, query_r);
  46. }
  47.  
  48. void modify(int vert, int vl_bnd, int vr_bnd, int left, int right, int val) {
  49.     push(vert, vl_bnd, vr_bnd);
  50.     if (right < vl_bnd || vr_bnd < left) {
  51.         return;
  52.     }
  53.  
  54.     if (left <= vl_bnd && vr_bnd <= right) {
  55.         Add_Mas[ vert ] = val;
  56.         push(vert, vl_bnd, vr_bnd);
  57.         return;
  58.     }
  59.  
  60.     int mid = vl_bnd + (vr_bnd - vl_bnd) / 2;
  61.     modify(2 * vert + 1, vl_bnd, mid, left, right, val);
  62.     modify(2 * vert + 2, mid + 1, vr_bnd, left, right, val);
  63.     Mas[ vert ] = max(Mas[ 2 * vert + 1 ], Mas[ 2 * vert + 2 ]);
  64. }
  65.  
  66.  
  67. int main() {
  68.     int cnt;
  69.     cin >> cnt;
  70.     int pow = 1;
  71.     while (pow < cnt) {
  72.         pow <<= 1;
  73.     }
  74.     Mas.resize(pow * 2, 0);
  75.     Add_Mas.resize(pow * 2, 0);
  76.     vector<int> tempio(pow, 0);
  77.     for (int i = 0; i < cnt; ++i) {
  78.         cin >> tempio[ i ];
  79.     }
  80.     build(0, 0, pow - 1, tempio);
  81.     int req = 0;
  82.     cin >> req;
  83.     for (int iter = 0; iter < req; ++iter) {
  84.         char todo;
  85.         cin >> todo;
  86.         if (todo == 'm') {
  87.             int lft, rht;
  88.             cin >> lft >> rht;
  89.             cout << query(0, 0, pow - 1, lft - 1, rht - 1) << " ";
  90.         } else {
  91.             int lft, rht, val;
  92.             cin >> lft >> rht >> val;
  93.             modify(0, 0, pow - 1, lft - 1, rht - 1, val);
  94.         }
  95.     }
  96.     return 0;
  97. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top