Advertisement
Vince14

/<> 17353 (lazy propagation seg special lazy array)

Sep 23rd, 2023
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 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, Q;
  25. long long arr[MAXN];
  26. long long seg[MAXN * 4];
  27. pair<long long, long long> lazy[MAXN * 4];
  28.  
  29. long long find_sum(int a, int b, long long start, long long inc){
  30.     int num = b + 1 - a;
  31.     return start * num + num * (num - 1) / 2 * inc;
  32. }
  33.  
  34. void prop(int x, int s, int e){
  35.     if(lazy[x].second == 0) return;
  36.     seg[x] += find_sum(s, e, lazy[x].first, lazy[x].second);
  37.     if(s != e){
  38.         int mid = (s + e) / 2;
  39.         int left_num = mid + 1 - s;
  40.         lazy[x * 2].first += lazy[x].first;
  41.         lazy[x * 2].second += lazy[x].second;
  42.         lazy[x * 2 + 1].first += lazy[x].first + left_num * lazy[x].second;
  43.         lazy[x * 2 + 1].second += lazy[x].second;
  44.     }
  45.     lazy[x] = {0, 0};
  46. }
  47.  
  48. void build(int x, int s, int e){
  49.     if(s == e){
  50.         seg[x] = arr[s];
  51.         return;
  52.     }
  53.     int mid = (s + e)/2;
  54.     build(x * 2, s, mid);
  55.     build(x * 2 + 1, mid + 1, e);
  56.     seg[x] = seg[x * 2] + seg[x * 2 + 1];
  57. }
  58.  
  59. void update(int x, int s, int e, int a, int b){
  60.     prop(x, s, e);
  61.     if(b < s or e < a) return;
  62.     if(a <= s and e <= b){
  63.         lazy[x].first += 1 + s - a;
  64.         lazy[x].second++;
  65.         prop(x, s, e);
  66.         return;
  67.     }
  68.     int mid = (s + e)/2;
  69.     update(x * 2, s, mid, a, b);
  70.     update(x * 2 + 1, mid + 1, e, a, b);
  71.     seg[x] = seg[x * 2] + seg[x * 2 + 1];
  72. }
  73.  
  74. long long query(int x, int s, int e, int idx){
  75.     prop(x, s, e);
  76.     if(idx < s or e < idx) return 0;
  77.     if(s == e) return seg[x];
  78.     int mid = (s + e)/2;
  79.     return query(x * 2, s, mid, idx) + query(x * 2 + 1, mid + 1, e, idx);
  80. }
  81.  
  82.  
  83. int main() {
  84.     FAST;
  85.     cin >> N;
  86.     for(int i = 1; i <= N; i++){
  87.         cin >> arr[i];
  88.     }
  89.     build(1, 1, N);
  90.     cin >> Q;
  91.     for(int a, b, i = 0; i < Q; i++){
  92.         cin >> a >> b;
  93.         if(a == 1){
  94.             int c;
  95.             cin >> c;
  96.             update(1, 1, N, b, c);
  97.         }
  98.         else{
  99.             cout << query(1, 1, N, b) << "\n";
  100.         }
  101.     }
  102. }
  103.  
  104. /*
  105. 5
  106. 1 2 1 2 1
  107. 4
  108. 1 1 5
  109. 2 5
  110. 1 2 5
  111. 2 5
  112.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement