fork download
  1. #include <iostream>
  2. #include <climits>
  3.  
  4. #define forn(i,a,b) for(int i = a; i < b; i++)
  5. #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define MAX 1310740
  7. #define M INT_MIN
  8.  
  9. using namespace std;
  10.  
  11. struct node
  12. {
  13. long long int prefix{0};
  14. long long int suffix{0};
  15. long long int sum{0};
  16. long long int best{0};
  17. public:
  18. node() = default;
  19. node(long long n)
  20. {
  21. prefix = suffix = sum = best = n;
  22. }
  23. node& operator=(long long n)
  24. {
  25. prefix = suffix = sum = best = n;
  26. return *this;
  27. }
  28. friend ostream& operator<<(ostream&, const node&);
  29. } tree[MAX];
  30.  
  31. ostream& operator<<(ostream& out, const node& nd)
  32. {
  33. out << "prefix: " << nd.prefix << endl;
  34. out << "suffix: " << nd.suffix << endl;
  35. out << "sum: " << nd.sum << endl;
  36. out << "best: " << nd.best << endl;
  37. return out;
  38. }
  39.  
  40. void constructST(int arr[], int ss, int se, int si)
  41. {
  42. if(ss > se) return;
  43. if(ss == se)
  44. {
  45. tree[si] = arr[ss];
  46. return;
  47. }
  48. int mid = ss + (se-ss)/2;
  49. constructST(arr, ss, mid, 2*si+1);
  50. constructST(arr, mid+1, se, 2*si+2);
  51. tree[si].best = tree[2*si+1].suffix + tree[2*si+2].prefix;
  52. tree[si].prefix = max(tree[2*si+1].prefix, tree[2*si+2].prefix + tree[2*si+1].sum);
  53. tree[si].suffix = max(tree[2*si+2].suffix, tree[2*si+2].sum + tree[2*si+1].suffix);
  54. tree[si].sum = tree[2*si+1].sum+tree[2*si+2].sum;
  55. if(tree[2*si+1].best > tree[si].best)
  56. {
  57. tree[si].best = tree[2*si+1].best;
  58. }
  59. else if(tree[2*si+2].best > tree[si].best)
  60. {
  61. tree[si].best = tree[2*si+2].best;
  62. }
  63. return;
  64. }
  65.  
  66. node getmax(int qs, int qe, int ss, int se, int si, int n)
  67. {
  68. //cout << "present index: " << si << endl;
  69. if(ss > qe || se < qs || qs > qe) return node(M);
  70. //cout << ss << " " << se << "\n" << tree[si] << endl;
  71.  
  72. if(ss >= qs && se <= qe) return tree[si];
  73.  
  74. int mid = ss + (se-ss)/2;
  75.  
  76. node left = getmax(qs,qe,ss,mid,2*si+1,n);
  77. node right = getmax(qs,qe,mid+1,se,2*si+2,n);
  78.  
  79. if(left.best == M) return right;
  80. else if(right.best == M) return left;
  81.  
  82. node ans(M);
  83.  
  84. ans.best = max(left.best, right.best);
  85. ans.best = max(ans.best, left.suffix + right.prefix);
  86. ans.prefix = max(left.prefix, left.sum+right.prefix);
  87. ans.suffix = max(right.suffix, right.sum+left.suffix);
  88. ans.sum = left.sum+right.sum;
  89. // if(si == 0)
  90. // {
  91. // cout << left << "\n" << right << "\n" << ans;
  92. // }
  93. return ans;
  94. }
  95.  
  96. int main()
  97. {
  98. boost;
  99. int n;
  100. cin >> n;
  101. int arr[n];
  102. forn(i,0,n)
  103. {
  104. cin >> arr[i];
  105. }
  106. constructST(arr,0,n-1,0);
  107. int m;
  108. cin >> m;
  109. while(m--)
  110. {
  111. int l, r;
  112. cin >> l >> r;
  113. l--;r--;
  114. cout << getmax(l,r,0,n-1,0,n).best << endl;
  115. }
  116. }
  117.  
Success #stdin #stdout 0s 4552KB
stdin
3 
-1 2 3
1
1 2
stdout
2