fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxx 1 << 16
  4. struct node
  5. {
  6. long pre;
  7. long suff;
  8. long sum;
  9. long maxsum;
  10. };
  11. struct node tree[maxx<<1];
  12. node merge(node &a,node &b)
  13. {
  14. node temp;
  15. temp.sum=a.sum+b.sum;
  16. temp.pre=max(a.pre,a.sum+b.pre);
  17. temp.suff=max(b.suff,b.sum+a.suff);
  18. temp.maxsum=max(max(temp.sum,temp.pre),temp.suff);
  19. return temp;
  20. }
  21. void build(int a[],int pos,int low,int high)
  22. {
  23. if(low==high)
  24. {
  25. tree[pos].maxsum=a[low];
  26. tree[pos].sum=a[low];
  27. tree[pos].pre=a[low];
  28. tree[pos].suff=a[low];
  29. return;
  30. }
  31. else
  32. {
  33. int mid=(low+high)>>1;
  34. build(a,2*pos,low,mid);
  35. build(a,2*pos+1,mid+1,high);
  36. tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
  37. }
  38. }
  39. node query(int pos,int low,int high,int qlow,int qhigh)
  40. {
  41. if(qlow>=low && qhigh<=high)tree[pos];
  42. int mid=(low+high)>>1;
  43. node l=query(2*pos,low,mid,qlow,qhigh);
  44. node r=query(2*pos+1,mid+1,high,qlow,qhigh);
  45. tree[pos]=merge(l,r);
  46. return tree[pos];
  47. }
  48. int main()
  49. {
  50. int n;
  51. cin>>n;
  52. int a[maxx];
  53. for(int i=0;i<n;i++)cin>>a[i];
  54. build(a,0,0,n-1);
  55. int Q;
  56. cin>>Q;
  57. while(Q--)
  58. {
  59. int x,y;
  60. cin>>x>>y;
  61. cout<<query(0,0,n-1,--x,--y).maxsum<<endl;
  62. }
  63. return 0;
  64. }
  65.  
Runtime error #stdin #stdout 0s 13248KB
stdin
3 
-1 2 3
1
1 2
stdout
Standard output is empty