Advertisement
Vince14

/<> 16975 (lazy propagation seg)

Sep 23rd, 2023
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<long long, long long>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 100005;
  23.  
  24. int N, M;
  25. int arr[MAXN];
  26. long long seg[MAXN * 4], lazy[MAXN * 4];
  27.  
  28. void prop(int x, int s, int e){
  29.     if(lazy[x] == 0) return;
  30.     seg[x] += lazy[x] * (e + 1 - s);
  31.     if(s == e){
  32.         lazy[x] = 0;
  33.     }
  34.     else{
  35.         lazy[x * 2] += lazy[x];
  36.         lazy[x * 2 + 1] += lazy[x];
  37.         lazy[x] = 0;
  38.     }
  39. }
  40.  
  41. void build(int x, int s, int e){
  42.     if(s == e){
  43.         seg[x] = arr[s];
  44.         return;
  45.     }
  46.     int mid = (s + e)/2;
  47.     build(x * 2, s, mid);
  48.     build(x * 2 + 1, mid + 1, e);
  49.     seg[x] = seg[x * 2] + seg[x * 2 + 1];
  50. }
  51.  
  52. void update(int x, int s, int e, int a, int b, int add){
  53.     prop(x, s, e);
  54.     if(e < a or b < s) return;
  55.     if(a <= s and e <= b){
  56.         lazy[x] += add;
  57.         prop(x, s, e);
  58.         return;
  59.     }
  60.     int mid = (s + e)/2;
  61.     update(x * 2, s, mid, a, b, add);
  62.     update(x * 2 + 1, mid + 1, e, a, b, add);
  63.     seg[x] = seg[x * 2] + seg[x * 2] + 1;
  64. }
  65.  
  66. long long query(int x, int s, int e, int idx){
  67.     prop(x, s, e);
  68.     if(idx < s or idx > e) return 0;
  69.     if(s == e){
  70.         return seg[x];
  71.     }
  72.     int mid = (s + e)/2;
  73.     return query(x * 2, s, mid, idx) + query(x * 2 + 1, mid + 1, e, idx);
  74. }
  75.  
  76. int main() {
  77.     FAST;
  78.     cin >> N;
  79.     for(int i = 1; i <= N; i++){
  80.         cin >> arr[i];
  81.     }
  82.     build(1, 1, N);
  83.     cin >> M;
  84.     for(int a, i = 1; i <= M; i++){
  85.         cin >> a;
  86.         if(a == 1){
  87.             int b, c, d;
  88.             cin >> b >> c >> d;
  89.             update(1, 1, N, b, c, d);
  90.         }
  91.         else{
  92.             int b;
  93.             cin >> b;
  94.             cout << query(1, 1, N, b) << "\n";
  95.         }
  96.     }
  97. }
  98.  
  99. /*
  100. 5
  101. 1 2 3 4 5
  102. 4
  103. 1 3 4 6
  104. 2 3
  105. 1 1 3 -2
  106. 2 3
  107.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement