Created
September 17, 2021 21:31
-
-
Save Rockbet/5406d9c22d95282bc00b85325331e8ee to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
const int maxn = 1e5+10; | |
int n, q, a[maxn]; | |
struct no{ | |
ll seg, pref, suf, sum; | |
no(){ | |
seg = pref = suf = sum = 0; | |
} | |
no(ll v){ | |
sum = v; | |
v = max(v, 0LL); | |
seg = pref = suf = v; | |
} | |
}tree[4*maxn]; | |
no join(no a, no b){ | |
no ans = 0; | |
ans.seg = max({a.seg, b.seg, a.suf + b.pref}); | |
ans.pref = max({a.pref, a.sum + b.pref}); | |
ans.suf = max({b.suf, b.sum + a.suf}); | |
ans.sum = a.sum + b.sum; | |
return ans; | |
} | |
void build(int node, int l, int r){ | |
if(l == r){ | |
tree[node] = a[l]; | |
return; | |
} | |
int mid = (l + r) >> 1; | |
build(2*node, l, mid), build(2*node+1, mid+1, r); | |
tree[node] = join(tree[2*node], tree[2*node+1]); | |
} | |
void update(int node, int tl, int tr, int pos, int val){ | |
if(tl == tr){ | |
a[pos] = val; | |
tree[node] = a[pos]; | |
return; | |
} | |
int mid = (tl + tr) >> 1; | |
if(pos <= mid) update(2*node, tl, mid, pos, val); | |
else update(2*node+1, mid+1, tr, pos, val); | |
tree[node] = join(tree[2*node], tree[2*node+1]); | |
} | |
no query(int node, int tl, int tr, int l, int r){ | |
if(tl > r or tr < l) return 0; | |
if(tl >= l and tr <= r) return tree[node]; | |
int mid = (tl + tr) >> 1; | |
return join(query(2*node, tl, mid, l, r), query(2*node+1, mid+1, tr, l, r)); | |
} | |
int main(){ | |
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); | |
cin >> n >> q; | |
for(int i=1; i<=n; i++) cin >> a[i]; | |
build(1, 1, n); | |
cout << query(1, 1, n, 1, n).seg << "\n"; | |
while(q--){ | |
int i, v; | |
cin >> i >> v; | |
update(1, 1, n, i+1, v); | |
cout << query(1, 1, n, 1, n).seg << "\n"; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment