fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. //#include "testlib.h"
  5. #define ff first
  6. #define ss second
  7. #define mp make_pair
  8. #define all(v) v.begin(),v.end()
  9. #define int long long
  10. #define ll long long
  11. #define M 1000000007
  12. #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
  13. #define GCD(m,n) __gcd(m,n)
  14. #define LCM(m,n) m*(n/GCD(m,n))
  15. #define mii map<ll ,ll >
  16. #define sz(a) (int)a.size()
  17. #define msi map<string,ll >
  18. #define mis map<ll int, string>
  19. #define rep(a,b) for(ll i=a;i<b;i++)
  20. #define rep0(n) for(ll i=0;i<n;i++)
  21. #define repi(i,a,b) for(ll i=a;i<b;i++)
  22. #define pb push_back
  23. #define vi vector<ll>
  24. #define mp make_pair
  25. #define vs vector<string>
  26. #define ppb pop_back
  27. #define endl '\n'
  28. #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  29. #define r0 return 0;
  30. #define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
  31. #define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
  32. #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  33. #define input freopen("input.txt", "r", stdin);
  34. #define Set(a, s) 4(a, s, sizeof (a))
  35. #define FOR repi
  36. #define pii pair<int,int>
  37. #define REVERSE(v) reverse(ALL(v))
  38. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl
  39. #define debug cerr<<"bhau"<<endl
  40. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  41. template <typename Arg1>
  42. void __f(const char* name, Arg1&& arg1){
  43. std::cerr << name << " : " << arg1 << endl;
  44. }
  45. template <typename Arg1, typename... Args>
  46. void __f(const char* names, Arg1&& arg1, Args&&... args){
  47. const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  48. }
  49. ll max(ll a, ll b) { return (a > b)? a : b;}
  50. int min(int a, int b) { return (a < b)? a : b;}
  51. void amax(int &a,int b){a=max(a,b)%M; }
  52. void amin(int &a,int b){ a=min(a,b)%M;}
  53. void inc(int &a,int b){a=(a+b)%M;}
  54. void dec(int &a,int b){a=(a-b+M)%M;}
  55. const int N=2e5+100,inf=0;
  56. int total[2*N];
  57. int pre[2*N];
  58. int suff[2*N];
  59. int ans[2*N];
  60. int n;
  61. void build(){
  62. for(int i=n-1;i>=0;i--) {total[i]=total[i<<1]+total[i<<1|1];pre[i]=max(pre[i<<1],total[i<<1]+pre[i<<1|1]);suff[i]=max(suff[i<<1|1],suff[i<<1]+total[i<<1|1]);ans[i]=max({ans[i<<1],ans[i<<1|1],pre[i<<1|1]+suff[i<<1]});}
  63. }
  64. void modify(int p,int x){
  65. p+=n;
  66. for(total[p]=suff[p]=pre[p]=ans[p]=x;p>1;p>>=1) {
  67.  
  68. total[p>>1]=total[p]+total[p^1];
  69. int right=max(p,p^1),left=min(p,p^1);
  70. pre[p>>1]=max(pre[left],total[left]+pre[right]);
  71. suff[p>>1]=max(suff[right],suff[left]+total[right]);
  72. ans[p>>1]=max({ans[left],ans[right],pre[right]+suff[left]});
  73. // trace(p>>1,p,p^1,total[p>>1],pre[p>>1],suff[p>>1],ans[p>>1]);
  74. }
  75. }
  76. int query(int l,int r){
  77. int tl,tr;tl=tr=0;
  78. int pl,pr;
  79. pl=pr=inf;
  80. pr=inf;
  81. int al,ar;
  82. al=ar=inf;
  83. int sl=inf,sr=inf;
  84. for(l+=n,r+=n;l<r;l>>=1,r>>=1){
  85. // trace(l,r);
  86. if(l&1) {
  87. al=max({al,ans[l],sl+pre[l]});
  88. pl=max(pl,tl+pre[l]);
  89. sl=max(suff[l],total[l]+sl);
  90.  
  91. tl+=total[l];
  92. l++;
  93. }
  94. if(r&1) {
  95. --r;
  96. ar=max({ar,ans[r],sr+pre[r]});
  97. pr=max(pre[r],total[r]+pr);
  98. sr=max(sr,tr+suff[r]);
  99. tr+=total[r];
  100. }
  101. // trace(pl,pr,sl,sr,al,ar,tl,tr);
  102. }
  103. int res;
  104. res=max({al,ar,pr+sl});
  105. return res;
  106. }
  107.  
  108.  
  109. int solve()
  110. {
  111. int q;cin>>n>>q;
  112. rep0(n) cin>>total[i+n];
  113. rep0(n) {pre[i]=suff[i]=ans[i]=inf;pre[n+i]=suff[n+i]=ans[n+i]=total[n+i];}
  114. build();
  115. while(q--){
  116. int k,x;cin>>k>>x;k--;
  117. modify(k,x);
  118. cout<<query(0,n)<<endl;
  119. }
  120. r0
  121. }
  122. signed main()
  123. {
  124. asdf
  125.  
  126. int t=1;
  127. //cin>>t;
  128. while(t--)
  129. {
  130. solve();
  131. }
  132.  
  133. }
Success #stdin #stdout 0s 4252KB
stdin
5 3
1 2 -3 5 -1
2 6
3 1
2 -2
stdout
9
13
6