Advertisement
Josif_tepe

Untitled

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