Advertisement
Josif_tepe

Untitled

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