fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class segment_tree {
  5.     using ll = long long;
  6.     struct segment {
  7.         ll seg, prefix, suffix, res;
  8.         friend segment merge(const segment &a, const segment &b) {
  9. 	        return segment( max(max(a.seg,b.seg),a.suffix+b.prefix),
  10. 	                        max(a.prefix,a.res+b.prefix),
  11. 	                        max(b.suffix,b.res+a.suffix),
  12. 	                        a.res+b.res); }
  13.         segment(ll s = 0, ll p = 0, ll q = 0, ll r = 0) :
  14.             seg(s), prefix(p), suffix(q), res(r) {} } phi;
  15.     static inline segment single_item(ll v) { 
  16.         ll u = max(v,0ll); return segment(u,u,u,v); }
  17.     vector<segment> s;
  18.     segment update(int k, int l, int r, int i, const segment &t) {
  19.         if (l == r)
  20.             return s[k] = t;
  21.         int m = (l+r)/2, p = m+1, u = 2*k, v = u+1;
  22.         return s[k] = (i < p ?  merge(update(u,l,m,i,t),s[v]) : 
  23.                                 merge(s[u],update(v,p,r,i,t))); }
  24.     segment query(int k, int l, int r, int n) const {
  25.         if (l > n or r < 1)
  26.             return phi;
  27.         if (l > 0 and r <= n)
  28.             return s[k];
  29.         int m = (l+r)/2, p = m+1, u = 2*k, v = u+1;
  30.         return merge(query(u,l,m,n),query(v,p,r,n)); }
  31. public:
  32.     segment_tree(int n) { s.resize(4*n); }
  33.     void update(int n, int i, int v) { update(1,1,n,i+1,single_item(v)); } 
  34.      ll query(int n) const { return query(1,1,n,n).seg; } };
  35.  
  36. int main() {
  37.     int n, q; 
  38.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cin >> n >> q;
  39.     segment_tree s(n);
  40.     for (int a, i = 0; i < n; ++i)
  41.         cin >> a, s.update(n,i,a);
  42.     cout << s.query(n) << '\n';
  43.     for (int i, v; q--; cout << s.query(n) << '\n')
  44.         cin >> i >> v, s.update(n,i,v); }
  45.  
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
5 2
5 -4 4 3 -5
4 3
3 -1
stdout
copy 
8
11
7
https://ideone.com/lSFFWq
Segment with the Maximum Sum
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!