fork(9) download
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long lld;
  4. typedef unsigned long long llu;
  5. #define rep(i,x,y) for(i=x;i<y;i++)
  6. #define rrep(i,x,y) for(i=x;i>=y;i--)
  7. #define trv(y,x) for(typeof(x.begin())y=x.begin();y!=x.end();y++)
  8. #define MID(x,y) (x+((y-x)/2))
  9. using namespace std;
  10.  
  11.  
  12. #define MAX (1<<16)
  13. #define MAX2 (MAX<<2)
  14.  
  15.  
  16.  
  17.  
  18. int A[MAX];
  19. struct node
  20. {
  21. int bestleftsum,bestrightsum,sum,bestsum;
  22. void Merge(node &A,node &B)
  23. {
  24. sum=A.sum+B.sum;
  25. bestleftsum=max(A.bestleftsum,A.sum+B.bestleftsum);
  26. bestrightsum=max(A.bestrightsum+B.sum,B.bestrightsum);
  27. bestsum=max(max(A.bestsum,B.bestsum),A.bestrightsum+B.bestleftsum);
  28. }
  29. void CreateLeaf(int val)
  30. {
  31. sum=bestleftsum=bestrightsum=bestsum=val;
  32. }
  33. };
  34.  
  35.  
  36.  
  37. node T[MAX2];
  38. void init(int index,int l,int r)
  39. {
  40. if(l==r)
  41. {
  42. T[index].CreateLeaf(A[l]);
  43. return;
  44. }
  45. else
  46. {
  47. int mid=MID(l,r);
  48. init(2*index,l,mid);
  49. init(2*index+1,mid+1,r);
  50. T[index].Merge(T[2*index],T[2*index+1]);
  51. }
  52.  
  53. }
  54. void query(node& result,int l,int r,int u,int v,int index)
  55. {
  56. if(u==l && v==r)
  57. {
  58. result=T[index];
  59. return;
  60. }
  61. else
  62. {
  63. int mid=MID(l,r);
  64. if(mid>=v)
  65. query(result,l,mid,u,v,2*index);
  66. else if(mid<u)
  67. query(result,mid+1,r,u,v,2*index+1);
  68. else
  69. {
  70. node left,right;
  71. query(left,l,mid,u,mid,2*index);
  72. query(right,mid+1,r,mid+1,v,2*index+1);
  73. result.Merge(left,right);
  74.  
  75. }
  76. }
  77. }
  78.  
  79. int main()
  80. {
  81. ios_base::sync_with_stdio(false);
  82. cin.tie(NULL);
  83. int n,t,x,y;
  84. cin>>n;
  85. for(int i=0;i<n;i++)
  86. cin>>A[i];
  87. init(1,0,n-1);
  88. cin>>t;
  89. node Ans;
  90. while(t--)
  91. {
  92. cin>>x>>y;
  93. query(Ans,0,n-1,x-1,y-1,1);
  94. cout<<Ans.bestsum<<"\n";
  95. }
  96.  
  97.  
  98.  
  99. return 0;
  100. }
Success #stdin #stdout 0s 7816KB
stdin
3 
-1 2 3
1
1 2
stdout
2