fork(2) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector <int> vi;
  6. typedef vector<vi> vvi;
  7. typedef pair<int,int> ii;
  8. #define pb push_back
  9. #define INF 100000000
  10. #define mp make_pair
  11. #define MOD 1000000007
  12. #define F first
  13. #define S second
  14.  
  15. int n;
  16. ll a[100005];
  17. ll total[200005];
  18. ll ans[200005];
  19. ll pref[200005];
  20. ll suff[200005];
  21.  
  22. int main() {
  23.  
  24. ios::sync_with_stdio(false);
  25. cin >> n;
  26. int x = 1;
  27. while (x < n) x *= 2;
  28.  
  29. for (int i = 0; i < n; i ++) cin >> a[i];
  30. for (int i = n; i < x; i++) a[i] = -(INF*INF);
  31.  
  32. n = x;
  33.  
  34. for (int i = n; i < 2*n; i++) total[i] = a[i-n];
  35. for (int i = n-1; i > 0; i--) total[i] = total[i*2]+total[i*2+1];
  36.  
  37. for (int i = n; i < 2*n; i++) pref[i] = a[i-n];
  38. for (int i = n-1; i > 0; i--) pref[i] = max(pref[i*2],total[i*2]+pref[i*2+1]);
  39.  
  40. for (int i = n; i < 2*n; i++) suff[i] = a[i-n];
  41. for (int i = n-1; i > 0; i--) suff[i] = max(suff[i*2+1],total[i*2+1]+suff[i*2]);
  42.  
  43. for (int i = n; i < 2*n; i++) ans[i] = a[i-n];
  44. for (int i = n-1; i > 0; i--) ans[i] = max(suff[i*2]+pref[i*2+1],
  45. max(ans[i*2],ans[i*2+1])
  46. );
  47.  
  48. // for (int i = 0; i < 2*n; i++) cout << i << " - " << ans[i] << endl;
  49.  
  50. int m;
  51. cin >> m;
  52. while (m --){
  53. ll l,r;
  54. cin >> l >> r;
  55. l --;
  56. l += n;
  57. r += n;
  58. ll res = -(INF*INF);
  59. ll prev = res;
  60. vector<ll> R1,R2;
  61.  
  62. while (l < r){
  63. if (l%2 == 1){
  64. // res = max(res,ans[l++]);
  65. l++;
  66. R1.pb(l-1);
  67. }
  68. if (r%2 == 1){
  69. // res = max(res,ans[--r]);
  70. --r;
  71. R2.pb(r);
  72. }
  73.  
  74. // cout << l << " " << r << " " << res << endl;
  75.  
  76. l /= 2;
  77. r /= 2;
  78. }
  79.  
  80. for (int i = R2.size()-1; i >= 0; i --) R1.pb(R2[i]);
  81.  
  82. for (int i = 0; i < R1.size(); i++){
  83. res = max(res,ans[R1[i]]);
  84. res = max(res,prev+pref[R1[i]]);
  85. prev = max(prev+total[R1[i]],suff[R1[i]]);
  86. }
  87.  
  88. cout << res << endl;
  89. }
  90. }
Success #stdin #stdout 0s 22272KB
stdin
10
-1 9 2 6 -4 3 5 2 -6 1
1
4 7
stdout
10