Advertisement
Josif_tepe

Untitled

Jun 10th, 2023
571
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. int a[maxn];
  6. int segment_tree[3 * maxn];
  7. int lazy_propagation[3 * maxn];
  8.  
  9. void build_tree(int L, int R, int position) {
  10.     if(L == R) {
  11.         segment_tree[position] = a[L];
  12.     }
  13.     else {
  14.         int middle = (L + R) / 2;
  15.         build_tree(L, middle, 2 * position);
  16.         build_tree(middle + 1, R, 2 * position + 1);
  17.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  18.     }
  19. }
  20.  
  21. void update_range(int L, int R, int position, int i, int j, int new_value) {
  22.     if(lazy_propagation[position] > 0) {
  23.         segment_tree[position] += lazy_propagation[position] * (R - L + 1);
  24.         if(L != R) {
  25.             lazy_propagation[2 * position] += lazy_propagation[position];
  26.             lazy_propagation[2 * position + 1] += lazy_propagation[position];
  27.         }
  28.         lazy_propagation[position] = 0;
  29.     }
  30.     // L R i L R j L R
  31.     if(R < i or j < L) {
  32.         return;
  33.     }
  34.     if(i <= L and R <= j) {
  35.         segment_tree[position] += new_value * (R - L + 1);
  36.         if(L != R) {
  37.             lazy_propagation[2 * position] += new_value;
  38.             lazy_propagation[2 * position + 1] += new_value;
  39.         }
  40.         return;
  41.     }
  42.     int middle = (L + R) / 2;
  43.     update_range(L, middle, 2 * position, i, j, new_value);
  44.     update_range(middle + 1, R, 2 * position + 1, i, j, new_value);
  45.     segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  46. }
  47. int query(int L, int R, int position, int i, int j) {
  48.     if(lazy_propagation[position] > 0) {
  49.         segment_tree[position] += lazy_propagation[position] * (R - L + 1);
  50.         if(L != R) {
  51.             lazy_propagation[2 * position] += lazy_propagation[position];
  52.             lazy_propagation[2 * position + 1] += lazy_propagation[position];
  53.         }
  54.         lazy_propagation[position] = 0;
  55.     }
  56.     //  L R i L R j L R
  57.     if(i <= L and R <= j) {
  58.         return segment_tree[position];
  59.     }
  60.     if(R < i or j < L) {
  61.         return 0;
  62.     }
  63.     int middle = (L + R) / 2;
  64.     return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j);
  65. }
  66. int main() {
  67.     ios_base::sync_with_stdio(false);
  68.     int n;
  69.     cin >> n;
  70.    
  71.     for(int i = 0; i < n; i++) {
  72.         cin >> a[i];
  73.     }
  74.     build_tree(0, n - 1, 1);
  75.     memset(lazy_propagation, 0, sizeof lazy_propagation);
  76.     int q;
  77.     cin >> q;
  78.    
  79.     for(int i = 0; i < q; i++) {
  80.         char c;
  81.         cin >> c;
  82.        
  83.         if(c == 'U') {
  84.             int a, b, x;
  85.             cin >> a >> b >> x;
  86.             update_range(0, n - 1, 1, a, b, x);
  87.             for(int j = 0; j < n; j++) {
  88.                 cout << query(0, n - 1, 1, j, j) << " ";
  89.             }
  90.             cout << endl;
  91.         }
  92.         else {
  93.             int a, b;
  94.             cin >> a >> b;
  95.             cout << query(0, n - 1, 1, a, b) << endl;
  96.         }
  97.     }
  98.     return 0;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement