fork download 
  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.  
  67. 		public SegmentTree query(int a, int b) {
  68. 			if (a == start && b == end)
  69. 				return this;
  70. 			int mid = (start + end) >> 1;
  71. 			if (a > mid)
  72. 				return right_child.query(a, b);
  73. 			else if (b <= mid)
  74. 				return left_child.query(a, b);
  75. 			SegmentTree st = new SegmentTree();
  76. 			join(st, left_child.query(a, mid), right_child.query(mid + 1, b));
  77. 			return st;
  78. 		}
  79.  
  80. 		public void update(int index, int value) {
  81. 			if (index == start && index == end) {
  82. 				bestleftsum = bestrightsum = bestsum = sum = value;
  83. 				return;
  84. 			}
  85. 			int mid = (start + end) >> 1;
  86. 			if (index <= mid)
  87. 				left_child.update(index, value);
  88. 			else
  89. 				right_child.update(index, value);
  90. 			join(this, left_child, right_child);
  91. 		}
  92. 	}
  93.  
  94. 	static class Reader {
  95. 		final private int BUFFER_SIZE = 1 << 16;
  96. 		private DataInputStream din;
  97. 		private byte[] buffer;
  98. 		private int bufferPointer, bytesRead;
  99.  
  100. 		public Reader() {
  101. 			din = new DataInputStream(System.in);
  102. 			buffer = new byte[BUFFER_SIZE];
  103. 			bufferPointer = bytesRead = 0;
  104. 		}
  105.  
  106. 		public Reader(String file_name) throws IOException {
  107. 			din = new DataInputStream(new FileInputStream(file_name));
  108. 			buffer = new byte[BUFFER_SIZE];
  109. 			bufferPointer = bytesRead = 0;
  110. 		}
  111.  
  112. 		public String readLine() throws IOException {
  113. 			byte[] buf = new byte[64];
  114. 			int cnt = 0, c;
  115. 			while ((c = read()) != -1) {
  116. 				if (c == '\n')
  117. 					break;
  118. 				buf[cnt++] = (byte) c;
  119. 			}
  120. 			return new String(buf, 0, cnt);
  121. 		}
  122.  
  123. 		public int nextInt() throws IOException {
  124. 			int ret = 0;
  125. 			byte c = read();
  126. 			while (c <= ' ')
  127. 				c = read();
  128. 			boolean neg = (c == '-');
  129. 			if (neg)
  130. 				c = read();
  131. 			do {
  132. 				ret = ret * 10 + c - '0';
  133. 			} while ((c = read()) >= '0' && c <= '9');
  134. 			if (neg)
  135. 				return -ret;
  136. 			return ret;
  137. 		}
  138.  
  139. 		public long nextLong() throws IOException {
  140. 			long ret = 0;
  141. 			byte c = read();
  142. 			while (c <= ' ')
  143. 				c = read();
  144. 			boolean neg = (c == '-');
  145. 			if (neg)
  146. 				c = read();
  147. 			do {
  148. 				ret = ret * 10 + c - '0';
  149. 			} while ((c = read()) >= '0' && c <= '9');
  150. 			if (neg)
  151. 				return -ret;
  152. 			return ret;
  153. 		}
  154.  
  155. 		public double nextDouble() throws IOException {
  156. 			double ret = 0, div = 1;
  157. 			byte c = read();
  158. 			while (c <= ' ')
  159. 				c = read();
  160. 			boolean neg = (c == '-');
  161. 			if (neg)
  162. 				c = read();
  163. 			do {
  164. 				ret = ret * 10 + c - '0';
  165. 			} while ((c = read()) >= '0' && c <= '9');
  166. 			if (c == '.')
  167. 				while ((c = read()) >= '0' && c <= '9')
  168. 					ret += (c - '0') / (div *= 10);
  169. 			if (neg)
  170. 				return -ret;
  171. 			return ret;
  172. 		}
  173.  
  174. 		private void fillBuffer() throws IOException {
  175. 			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  176. 			if (bytesRead == -1)
  177. 				buffer[0] = -1;
  178. 		}
  179.  
  180. 		private byte read() throws IOException {
  181. 			if (bufferPointer == bytesRead)
  182. 				fillBuffer();
  183. 			return buffer[bufferPointer++];
  184. 		}
  185.  
  186. 		public void close() throws IOException {
  187. 			if (din == null)
  188. 				return;
  189. 			din.close();
  190. 		}
  191. 	}
  192. }
  193. /*
  194.  * 4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3
  195.  */
  196. /*
  197.  * 10 -200 3 4 -200 6 2 4 -200 5 6 4 1 1 10 0 1 -100 1 1 5 1 1 10
  198.  */
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
10
-200 3 4 -200 6 2 4 -200 5 6
4
1 1 10
0 1 100
1 1 5
1 1 10
stdout 
12
107
107
https://ideone.com/2QbqYA
language:
Java (HotSpot 12)
created:
10 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!