fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12.  
  13. int n, q; 
  14. int a[N];  
  15.  
  16. struct Node {
  17. 	ll max_subarray, max_pref, max_suf, sum;  
  18.  
  19. 	Node() {}
  20.  
  21. 	Node(ll x) {
  22. 		max_subarray = max_pref = max_suf = max(0ll, x);   
  23. 		sum = x;  
  24. 	}
  25.  
  26. 	Node operator+(const Node& other) const {
  27. 		Node res; 
  28. 		res.max_subarray = max({max_subarray, other.max_subarray, max_suf + other.max_pref});
  29. 		res.max_pref = max(max_pref, sum + other.max_pref); 
  30. 		res.max_suf = max(other.max_suf, other.sum + max_suf);   
  31. 		res.sum = sum + other.sum; 
  32. 		return res;   
  33. 	}
  34. }; 
  35.  
  36. Node seg[4 * N]; 
  37.  
  38. void build(int id, int l, int r) {
  39. 	if (l == r) {
  40. 		seg[id] = Node(a[l]); 
  41. 		return; 
  42. 	}
  43. 	int mid = (l + r) >> 1; 
  44. 	build(id * 2, l, mid); 
  45. 	build(id * 2 + 1, mid + 1, r); 
  46. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  47. }
  48.  
  49. void update(int id, int l, int r, int pos, int val) {
  50. 	if (l > pos || r < pos) return;  
  51. 	if (l == r) {
  52. 		seg[id] = Node(val); 
  53. 		return;
  54. 	}
  55. 	int mid = (l + r) >> 1; 
  56. 	update(id * 2, l, mid, pos, val); 
  57. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  58. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  59. }
  60.  
  61. int main() {
  62. 	ios::sync_with_stdio(false); 
  63. 	cin.tie(nullptr);  	
  64. 	cin >> n >> q;  
  65. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  66.  
  67. 	build(1, 1, n); 
  68.  
  69. 	while (q--) {
  70. 		int pos, val; 
  71. 		cin >> pos >> val; 
  72. 		update(1, 1, n, pos, val); 
  73. 		cout << seg[1].max_subarray << '\n'; 
  74. 	}
  75. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5 3
1 2 -3 5 -1
2 6
3 1
2 -2
stdout
copy 
9
13
6
https://ideone.com/Tu38Vg
language:
C++14 (gcc 8.3)
created:
39 days 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!