fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 50001
  4. #define ll long long int
  5. #define IM INT_MAX
  6. ll sum[MAX+1];
  7. struct segment
  8. {
  9. 	ll pfx;
  10. 	ll sfx;
  11. 	ll best_sum;
  12.  
  13. };
  14.  
  15. segment query(segment *tree,ll index,ll s,ll e,ll qs,ll qe)
  16. {
  17. 	//3 cases
  18.  
  19. 	//1. no overlapping case
  20. 	if(s>e||qs>e || qe<s)
  21. 	{
  22. 		//return infinity
  23. 		segment ans;
  24. 		ans.pfx=-IM;
  25. 		ans.sfx=-IM;
  26. 		ans.best_sum=-IM;
  27. 		return ans;
  28. 	}
  29.  
  30. 	//2.complete overlapping
  31.  
  32. 	if(s>=qs && e<=qe)
  33. 	{
  34. 		return tree[index];
  35. 	}
  36.  
  37. 	//3. partial overlapping call both the sides
  38.  
  39. 	//splitting the range
  40. 	ll mid=(s+e)/2;
  41.  
  42. 	segment left=query(tree,2*index,s,mid,qs,qe);
  43. 	segment right=query(tree,2*index+1,mid+1,e,qs,qe);
  44.  
  45. 	segment res;
  46.  
  47. 	//pfx=max(left(pfx,left(sum)+right(pfx))
  48. 	if(s==0)
  49. 	res.pfx=max(left.pfx,sum[mid]+right.pfx);
  50. 	else
  51. 	res.pfx=max(left.pfx,sum[mid]-sum[s-1]+right.pfx);
  52.  
  53. 	//sfx=max(right(sfx),left(sfx)+right(sum))
  54. 	res.sfx=max(right.sfx,sum[e]-sum[mid]+left.sfx);
  55.  
  56. 	//best=max(pfx(of that node),sfx(of that node),best left sum,best right sum,left(sfx)+right(pfx)
  57. 	res.best_sum=max(max(left.best_sum,right.best_sum),left.sfx+right.pfx);
  58.  
  59. 	return res;
  60.  
  61. }
  62.  
  63. void update(segment *tree,ll index,ll s,ll e,ll pos,ll value)
  64. {
  65.  
  66. 	//no overlap
  67. 	if(pos <s || pos >e)
  68. 	return;
  69.  
  70. 	//complete overlap
  71. 	//leaf node
  72. 	if(s==e)
  73. 	{
  74. 		tree[index].pfx=value;
  75. 		tree[index].sfx=value;
  76. 		tree[index].best_sum=value;
  77.  
  78. 		return;
  79.  
  80.  
  81. 	}
  82.  
  83. 	//partial overlap
  84. 	int mid=(s+e)/2;
  85.  
  86. 	//left
  87.  
  88. 	update(tree,2*index,s,mid,pos,value);
  89. 	//right
  90.  
  91. 	update(tree,2*index+1,mid+1,e,pos,value);
  92.  
  93. 	if(s==0)
  94. 	tree[index].pfx=max(tree[2*index].pfx,sum[mid]+tree[2*index+1].pfx);
  95. 	else
  96. 	tree[index].pfx=max(tree[2*index].pfx,sum[mid]-sum[s-1]+tree[2*index+1].pfx);
  97.  
  98. 	//sfx=max(right(sfx),left(sfx)+right(sum))
  99. 	tree[index].sfx=max(tree[2*index+1].sfx,sum[e]-sum[mid]+tree[2*index].sfx);
  100.  
  101. 	//best=max(pfx(of that node),sfx(of that node),best left sum,best right sum,left(sfx)+right(pfx)
  102. 	tree[index].best_sum=max(max(tree[2*index].best_sum,tree[2*index+1].best_sum),tree[2*index].sfx+tree[2*index+1].pfx);
  103.  
  104. }
  105.  
  106. void buildtree(segment *tree,ll *a,ll index,ll s,ll e)
  107. {
  108. 	//tree is build bottom up
  109. 	if(s>e)
  110. 	return;
  111.  
  112. 	//filling the leaf nodes
  113. 	if(s==e)
  114. 	{
  115. 		tree[index].pfx=a[s];
  116. 		tree[index].sfx=a[s];
  117.  
  118. 		tree[index].best_sum=a[s];
  119. 		return;
  120. 	}
  121.  
  122. 	ll mid=(s+e)/2;
  123.  
  124. 	//left tree
  125. 	buildtree(tree,a,2*index,s,mid);
  126. 	//right tree
  127. 	buildtree(tree,a,2*index+1,mid+1,e);
  128.  
  129. 	//pfx=max(left(pfx,left(sum)+right(pfx))
  130. 	if(s==0)
  131. 	tree[index].pfx=max(tree[2*index].pfx,sum[mid]+tree[2*index+1].pfx);
  132. 	else
  133. 	tree[index].pfx=max(tree[2*index].pfx,sum[mid]-sum[s-1]+tree[2*index+1].pfx);
  134.  
  135. 	//sfx=max(right(sfx),left(sfx)+right(sum))
  136. 	tree[index].sfx=max(tree[2*index+1].sfx,sum[e]-sum[mid]+tree[2*index].sfx);
  137.  
  138. 	//best=max(pfx(of that node),sfx(of that node),best left sum,best right sum,left(sfx)+right(pfx)
  139. 	tree[index].best_sum=max(max(tree[2*index].best_sum,tree[2*index+1].best_sum),tree[2*index].sfx+tree[2*index+1].pfx);
  140.  
  141.  
  142.  
  143.  
  144.  
  145. }
  146. int main()
  147. {
  148. 	ll n;
  149. 	scanf("%lli",&n);
  150. 	ll a[n];
  151. 	for(ll i=0;i<n;i++)
  152. 	{
  153. 		scanf("%lli",&a[i]);
  154. 	}
  155.  
  156.           sum[0] = a[0];
  157.         for(ll i=1;i<n;i++) 
  158.           sum[i] = a[i] +sum[i-1];
  159. 	//allocating 4n+1 node size
  160.  
  161. 	segment *tree=new segment[4*n+1];
  162.  
  163.  
  164.  
  165. 	buildtree(tree,a,1,0,n-1);
  166.  
  167. 	ll m;
  168. 	scanf("%lli",&m);
  169. 	while(m--)
  170. 	{
  171.  
  172. 	ll id,x,y;
  173. 	scanf("%lli %lli %lli",&id,&x,&y);
  174. 	if(id==1)
  175. 	{
  176. 	printf("%lli",query(tree,1,0,n-1,x-1,y-1).best_sum);
  177. 	printf("\n");
  178. 	}
  179. 	if(id==0)
  180. 	{
  181. 		a[x-1]=y;
  182. 		update(tree,1,0,n-1,x-1,y);
  183. 	}
  184. 	}
  185. 	delete []tree;
  186. 	return 0;
  187. }
  188.  
Success #stdin #stdout 0s 4208KB
comments (?)
stdin
copy 
4
1 2 3 4
2
0 3 -3
1 2 4
stdout
copy 
9
https://ideone.com/ZTwJ1i
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!