fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAXN 50001
  5.  
  6. class Data
  7. {
  8. public:
  9. 	int sum, prefix, middle, suffix, best;
  10. 	Data()
  11. 	{
  12. 		sum = prefix = middle = suffix = best = -15008;
  13. 	}
  14. };
  15.  
  16. int ar[MAXN];
  17. Data tree[MAXN<<2];
  18.  
  19. class SegmentTree
  20. {
  21. 	int n;
  22.  
  23. 	void set(int node, int val)
  24. 	{
  25. 		tree[node].sum = tree[node].prefix = tree[node].middle = tree[node].suffix = tree[node].best = val;
  26. 	}
  27.  
  28. 	void calc(int node, Data &d, Data &lChild, Data &rChild)
  29. 	{
  30. 		d.sum = lChild.sum + rChild.sum;
  31. 		d.prefix = max(lChild.prefix, lChild.sum + rChild.prefix);
  32. 		d.suffix = max(rChild.suffix, lChild.suffix + rChild.sum);
  33. 		d.middle = lChild.suffix + rChild.prefix;
  34. 		d.best = max({d.sum, d.prefix, d.middle, d.suffix, lChild.best, rChild.best});
  35. 	}
  36.  
  37. 	void build(int s, int e, int node)
  38. 	{
  39. 		if(s==e) //leaf
  40. 			set(node,ar[s]);
  41. 		else
  42. 		{
  43. 			int m = s + (e-s)/2;
  44. 			build(s,m,2*node);
  45. 			build(m+1,e,2*node+1);
  46. 			calc(node,tree[node],tree[2*node],tree[2*node+1]);
  47. 		}
  48. 	}
  49.  
  50. 	Data query(int l, int r, int s, int e, int node)
  51. 	{
  52. 		Data d;
  53. 		if(s>r || e<l)
  54. 			return d;
  55. 		else if(s>=l && e<=r)
  56. 			return tree[node];
  57.  
  58. 		int m = s+(e-s)/2;
  59. 		if(l>m)
  60. 			return query(l,r,m+1,e,2*node+1);
  61. 		else if(r<=m)
  62. 			return query(l,r,s,m,2*node);
  63. 		else
  64. 		{
  65. 			Data lQuery = query(l,r,s,m,2*node);
  66. 			Data rQuery = query(l,r,m+1,e,2*node+1);
  67. 			calc(node,d,lQuery,rQuery);
  68. 			return d;
  69. 		}
  70. 	}
  71.  
  72. public:
  73. 	SegmentTree(int n)
  74. 	{
  75. 		this->n = n;
  76. 		build(1,n,1);
  77. 	}
  78.  
  79. 	int query(int l, int r)
  80. 	{
  81. 		return query(l,r,1,n,1).best;
  82. 	}
  83.  
  84. };
  85.  
  86. int main()
  87. {
  88. 	int n; scanf("%d",&n);
  89. 	for(int i=1;i<=n;i++)
  90. 		scanf("%d",&ar[i]);
  91.  
  92. 	SegmentTree st(n);
  93. 	int q; scanf("%d",&q);
  94. 	while(q--)
  95. 	{
  96. 		int l,r;
  97. 		scanf("%d%d",&l,&r);
  98. 		printf("%d\n",st.query(l,r));
  99. 	}
  100. 	return 0;
  101. }
  102.  
Success #stdin #stdout 0s 7584KB
comments (?)
stdin
copy 
3
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/AVZs4f
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!