• API
• FAQ
• Tools
• Archive
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;
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);
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.
Not a member of Pastebin yet?