Advertisement
Josif_tepe

Untitled

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