fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5.  
  6. class GSS3 {
  7. 	static int array[];
  8.  
  9. 	public static void main(String[] args) throws IOException {
  10. 		// TODO Auto-generated method stub
  11. 		GSS3.Reader r = new GSS3.Reader();
  12. 		int N = r.nextInt();
  13. 		array = new int[N + 1];
  14. 		for (int i = 1; i <= N; i++) {
  15. 			array[i] = r.nextInt();
  16. 		}
  17. 		SegmentTree st = new SegmentTree(1, N);
  18. 		int Q = r.nextInt();
  19. 		StringBuilder sb = new StringBuilder();
  20. 		PrintWriter pr = new PrintWriter(System.out);
  21. 		for (int i = 0; i < Q; i++) {
  22. 			int choice = r.nextInt();
  23. 			int left = r.nextInt();
  24. 			int right = r.nextInt();
  25. 			if (choice == 1) {
  26. 				sb.append(st.query(left, right).bestsum + "\n");
  27. 			} else {
  28. 				st.update(left, right);
  29. 			}
  30. 		}
  31. 		pr.write(sb.toString());
  32. 		pr.flush();
  33. 	}
  34.  
  35. 	static class SegmentTree {
  36. 		SegmentTree left_child, right_child;
  37. 		int bestleftsum, bestrightsum, bestsum, sum, start, end;
  38.  
  39. 		public SegmentTree() {
  40. 		}
  41.  
  42. 		public SegmentTree(int a, int b) {
  43. 			start = a;
  44. 			end = b;
  45. 			if (start != end) {
  46. 				int mid = (start+end) >> 1;
  47. 				left_child = new SegmentTree(start, mid);
  48. 				right_child = new SegmentTree(mid + 1, end);
  49. 				join(this, left_child, right_child);
  50. 			} else {
  51. 				bestleftsum = bestrightsum = bestsum = sum = GSS3.array[start];
  52. 			}
  53. 		}
  54.  
  55. 		public void join(SegmentTree parent, SegmentTree left_child, SegmentTree right_child) {
  56. 			parent.sum = left_child.sum + right_child.sum;
  57. 			parent.bestleftsum = Math.max(left_child.bestleftsum, left_child.sum + right_child.bestleftsum);
  58. 			parent.bestrightsum = Math.max(right_child.bestrightsum, right_child.sum + left_child.bestrightsum);
  59. 			/*parent.bestsum = Math.max(
  60. 					left_child.bestleftsum,
  61. 					Math.max(
  62. 							right_child.bestrightsum,
  63. 							Math.max(left_child.bestrightsum, Math.max(right_child.bestleftsum, left_child.bestrightsum
  64. 									+ right_child.bestleftsum))));
  65. 		*/
  66. 		parent.bestsum=Math.max(left_child.bestsum, Math.max(right_child.bestsum,left_child.bestrightsum+right_child.bestleftsum));
  67. 		}
  68.  
  69. 		public SegmentTree query(int a, int b) {
  70. 			if (a == start && b == end)
  71. 				return this;
  72. 			int mid = (start + end) >> 1;
  73. 			if (a > mid)
  74. 				return right_child.query(a, b);
  75. 			else if (b <= mid)
  76. 				return left_child.query(a, b);
  77. 			SegmentTree st = new SegmentTree();
  78. 			join(st, left_child.query(a, mid), right_child.query(mid + 1, b));
  79. 			return st;
  80. 		}
  81.  
  82. 		public void update(int index, int value) {
  83. 			if (index == start && index == end) {
  84. 				bestleftsum = bestrightsum = bestsum = sum = value;
  85. 				return;
  86. 			}
  87. 			int mid = (start + end) >> 1;
  88. 			if (index <= mid)
  89. 				left_child.update(index, value);
  90. 			else
  91. 				right_child.update(index, value);
  92. 			join(this, left_child, right_child);
  93. 		}
  94. 	}
  95.  
  96. 	static class Reader {
  97. 		final private int BUFFER_SIZE = 1 << 16;
  98. 		private DataInputStream din;
  99. 		private byte[] buffer;
  100. 		private int bufferPointer, bytesRead;
  101.  
  102. 		public Reader() {
  103. 			din = new DataInputStream(System.in);
  104. 			buffer = new byte[BUFFER_SIZE];
  105. 			bufferPointer = bytesRead = 0;
  106. 		}
  107.  
  108. 		public Reader(String file_name) throws IOException {
  109. 			din = new DataInputStream(new FileInputStream(file_name));
  110. 			buffer = new byte[BUFFER_SIZE];
  111. 			bufferPointer = bytesRead = 0;
  112. 		}
  113.  
  114. 		public String readLine() throws IOException {
  115. 			byte[] buf = new byte[64];
  116. 			int cnt = 0, c;
  117. 			while ((c = read()) != -1) {
  118. 				if (c == '\n')
  119. 					break;
  120. 				buf[cnt++] = (byte) c;
  121. 			}
  122. 			return new String(buf, 0, cnt);
  123. 		}
  124.  
  125. 		public int nextInt() throws IOException {
  126. 			int ret = 0;
  127. 			byte c = read();
  128. 			while (c <= ' ')
  129. 				c = read();
  130. 			boolean neg = (c == '-');
  131. 			if (neg)
  132. 				c = read();
  133. 			do {
  134. 				ret = ret * 10 + c - '0';
  135. 			} while ((c = read()) >= '0' && c <= '9');
  136. 			if (neg)
  137. 				return -ret;
  138. 			return ret;
  139. 		}
  140.  
  141. 		public long nextLong() throws IOException {
  142. 			long ret = 0;
  143. 			byte c = read();
  144. 			while (c <= ' ')
  145. 				c = read();
  146. 			boolean neg = (c == '-');
  147. 			if (neg)
  148. 				c = read();
  149. 			do {
  150. 				ret = ret * 10 + c - '0';
  151. 			} while ((c = read()) >= '0' && c <= '9');
  152. 			if (neg)
  153. 				return -ret;
  154. 			return ret;
  155. 		}
  156.  
  157. 		public double nextDouble() throws IOException {
  158. 			double ret = 0, div = 1;
  159. 			byte c = read();
  160. 			while (c <= ' ')
  161. 				c = read();
  162. 			boolean neg = (c == '-');
  163. 			if (neg)
  164. 				c = read();
  165. 			do {
  166. 				ret = ret * 10 + c - '0';
  167. 			} while ((c = read()) >= '0' && c <= '9');
  168. 			if (c == '.')
  169. 				while ((c = read()) >= '0' && c <= '9')
  170. 					ret += (c - '0') / (div *= 10);
  171. 			if (neg)
  172. 				return -ret;
  173. 			return ret;
  174. 		}
  175.  
  176. 		private void fillBuffer() throws IOException {
  177. 			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  178. 			if (bytesRead == -1)
  179. 				buffer[0] = -1;
  180. 		}
  181.  
  182. 		private byte read() throws IOException {
  183. 			if (bufferPointer == bytesRead)
  184. 				fillBuffer();
  185. 			return buffer[bufferPointer++];
  186. 		}
  187.  
  188. 		public void close() throws IOException {
  189. 			if (din == null)
  190. 				return;
  191. 			din.close();
  192. 		}
  193. 	}
  194. }
  195. /*
  196.  * 4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3
  197.  */
  198. /*
  199.  * 10 -200 3 4 -200 6 2 4 -200 5 6 4 1 1 10 0 1 -100 1 1 5 1 1 10
  200.  */
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
stdout
copy 
6
4
-3
https://ideone.com/wgs4pS
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!