fork(2) download
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. #define left(i) (2*i + 1)
  5. #define right(i) (2*i + 2)
  6. #define parent(i) ((i-1)/2)
  7. #include <vector>
  8.  
  9. template<class T>
  10. class SegmentTree
  11. {
  12. public:
  13. SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  14. SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  15. T query(int l, int r);
  16. void update(int idx, T val);
  17. //TODO lazy propagation
  18. private:
  19. T *tree;
  20. void buildTree(std::vector<T> data);
  21. int segTreeSize;
  22. T valueForExtraNodes;
  23. T (*combine)(T obj1, T obj2);
  24. int calculateSize(int n);
  25. T queryHelper(int l,int r, int st, int ed, int node);
  26. };
  27.  
  28. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  29. T value, T (*combine)(T obj1, T obj2))
  30. {
  31. this->combine = combine;
  32. valueForExtraNodes = value;
  33. segTreeSize = calculateSize(data.size());
  34. buildTree(data);
  35. }
  36.  
  37. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  38. T value, T (*combine)(T obj1, T obj2))
  39. {
  40. this->combine = combine;
  41. valueForExtraNodes = value;
  42. segTreeSize = calculateSize(n);
  43.  
  44. std::vector<T> data;
  45. for(int i = 0; i < n; i++)
  46. data.push_back(ar[i]);
  47.  
  48. buildTree(data);
  49. }
  50.  
  51.  
  52. template<class T> int SegmentTree<T>::calculateSize(int n)
  53. {
  54. int pow2 = 1;
  55. while( pow2 < n)
  56. {
  57. pow2 = pow2 << 1;
  58. }
  59. return 2*pow2 - 1;
  60. }
  61.  
  62. template<class T> T SegmentTree<T>::query(int l, int r)
  63. {
  64. int st = 0, ed = segTreeSize/2;
  65. return queryHelper(l, r, st, ed, 0);
  66. }
  67.  
  68. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  69. {
  70. if( (r < st) || (l > ed) || (l > r) )
  71. return valueForExtraNodes;
  72. if(st >= l && ed <= r)
  73. return tree[node];
  74. T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  75. T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  76. return combine(leftVal, rightVal);
  77. }
  78.  
  79. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  80. {
  81. int n = data.size();
  82. tree = new T[segTreeSize];
  83. int extraNodes = (segTreeSize/2 + 1) - n;
  84. for(int i = segTreeSize - 1; i >= 0; i--)
  85. {
  86. if(extraNodes>0)
  87. {
  88. tree[i] = valueForExtraNodes;
  89. extraNodes--;
  90. }
  91. else if(n>0)
  92. {
  93. tree[i] = data[n-1];
  94. n--;
  95. }
  96. else
  97. tree[i] = combine(tree[left(i)], tree[right(i)]);
  98. }
  99. }
  100.  
  101. template<class T> void SegmentTree<T>::update(int idx, T val)
  102. {
  103. int segTreeIdx = (segTreeSize/2) + idx;
  104. tree[segTreeIdx] = val;
  105. while(parent(segTreeIdx) >= 0)
  106. {
  107. segTreeIdx = parent(segTreeIdx);
  108. if(right(segTreeIdx) < segTreeSize)
  109. tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  110. if(segTreeIdx == 0)
  111. break;
  112. }
  113. }
  114.  
  115. struct node
  116. {
  117. int ans; int tot;
  118. int pref;
  119. int suf;
  120. node(){}
  121. node(int val){tot=ans=pref=suf=val;}
  122. };
  123. node combine(node x,node y)
  124. {
  125. node *ptr = new node();
  126. ptr->ans = max(x.ans,y.ans);
  127. ptr->ans = max(ptr->ans,y.pref+x.suf);
  128. ptr->pref = max(x.tot+y.pref,x.pref);
  129. ptr->suf = max(y.tot+x.suf,y.suf);
  130. ptr->tot = x.tot+y.tot;
  131. return *ptr;
  132. }
  133. int main()
  134. {
  135. int t,i,j,n,ans;
  136. cin>>n;
  137. vector<node> v(n);
  138. for(i=0;i<n;i++)
  139. {
  140. cin>>j;
  141. v[i] = node(j);
  142. }
  143. SegmentTree<node> sg(v,node(-20000),combine);
  144. cin>>n;
  145. while(n--)
  146. {
  147. cin>>i>>j;
  148. node as = sg.query(i-1,j-1);
  149. cout<<(as.ans)<<endl;
  150. }
  151. return 0;
  152. }
  153.  
  154.  
Success #stdin #stdout 0s 4484KB
stdin
3 
-1 2 3
1
1 2
stdout
2