fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.InputStream;
  3.  
  4. class segTreeNode{
  5. 	int preMaxSum;
  6. 	int sufMaxSum;
  7. 	int maxSum;
  8. 	int sum;
  9. 	public void addtoleaf(int value)
  10. 	{
  11. 		preMaxSum = value;
  12. 		sufMaxSum = value;
  13. 		maxSum = value;
  14. 		sum = value;
  15. 	}
  16. 	public void mergetree(segTreeNode left , segTreeNode right)
  17. 	{
  18.  
  19. 		sum = left.sum+right.sum;
  20. 		preMaxSum = Math.max(left.preMaxSum, left.sum+right.preMaxSum);
  21. 		sufMaxSum = Math.max(right.sufMaxSum,right.sum+left.sufMaxSum);
  22. 		maxSum = Math.max(preMaxSum, Math.max(sufMaxSum, Math.max(left.maxSum, Math.max(right.maxSum, left.sufMaxSum+right.preMaxSum))));
  23. 	}
  24. 	public int getValue()
  25. 	{
  26. 		return maxSum;
  27. 	}
  28. }
  29. public class Main {
  30. 	static segTreeNode[]  nodes ;
  31. 	//static int abc = 5;
  32. 	public int getSize(int n)
  33. 	{
  34. 		int size = 1;
  35. 		for(;size<n;size= size<<1);
  36. 		return size<<1;
  37. 	}
  38. 	Main(int[]arr)
  39. 	{
  40. 		nodes = new segTreeNode[getSize(arr.length)];
  41. 		build(arr,0,arr.length-1,1);
  42. 	}
  43. 	public static void build(int[] arr, int as, int ae, int index)
  44. 	{
  45. 		if(as == ae)
  46. 		{
  47. 			segTreeNode stc = new segTreeNode();
  48. 			stc.addtoleaf(arr[as]);
  49. 			nodes[index]= stc;
  50. 			return;
  51. 		}
  52. 		int mid = as+(ae-as)/2;
  53. 		int left = 2*index;
  54. 		int right = left+1;
  55. 		build(arr,as,mid,left);
  56. 		build(arr,mid+1,ae,right);
  57. 		nodes[index] = new segTreeNode();
  58. 		nodes[index].mergetree(nodes[left], nodes[right]);
  59.  
  60. 	}
  61. 	public static segTreeNode query(int index ,int qs, int qe, int as, int ae)
  62. 	{
  63. 		if(qs == as && qe == ae)
  64. 		{
  65. 			return nodes[index];
  66. 		}
  67. 		int mid = as+(ae-as)/2;
  68. 		if(qs>mid)
  69. 			return query(2*index+1, qs, qe, mid+1, ae);
  70. 		if(qe<=mid)
  71. 			return query(2*index,qs,qe,as,mid);
  72. 		segTreeNode left = query(2*index, qs, mid, as, mid);
  73. 		segTreeNode right = query(2*index+1,mid+1,qe,mid+1,ae);
  74. 		segTreeNode res = new segTreeNode();
  75. 		res.mergetree(left, right);
  76. 		return res;
  77. 	}
  78. 	public static void main(String[] args) throws Exception {
  79. 		Parser p = new Parser(System.in);
  80. 		int no = p.nextInt();
  81. 		int[]arr = new int[no];
  82. 		for(int i = 0;i<no;i++)
  83. 			arr[i] = p.nextInt();
  84. 		Main m = new Main(arr);
  85. 		int q = p.nextInt();
  86. 		while(q>0)
  87. 		{
  88. 			q--;
  89. 		segTreeNode  st =	Main.query(1, p.nextInt()-1, p.nextInt()-1, 0, no-1);
  90. 		System.out.println(st.maxSum);
  91. 		}
  92. 	}
  93. }
  94. class Parser
  95. {final private int BUFFER_SIZE=1<<16;private DataInputStream din;private byte[]buffer;private int bufferPointer,bytesRead;public Parser(InputStream in)
  96. {din=new DataInputStream(in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;}
  97. public long nextLong()throws Exception
  98. {long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=c=='-';if(neg)c=read();do
  99. {ret=ret*10+c-'0';c=read();}while(c>' ');if(neg)return-ret;return ret;}
  100. public String next()throws Exception
  101. {StringBuilder ret=new StringBuilder();byte c=read();while(c<=' ')c=read();do
  102. {ret=ret.append((char)c);c=read();}while(c>' ');return ret.toString();}
  103. public int nextInt()throws Exception
  104. {int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=c=='-';if(neg)c=read();do
  105. {ret=ret*10+c-'0';c=read();}while(c>' ');if(neg)return-ret;return ret;}
  106. private void fillBuffer()throws Exception
  107. {bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;}
  108. private byte read()throws Exception
  109. {if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];}}
  110.  
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
10 
-200 3 4 -200 6 2 4 -200 5 6 
1 
1 10
stdout
copy 
12
https://ideone.com/rBmcNZ
language:
Java (HotSpot 12)
created:
9 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!