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

Case #2:
40
26
https://ideone.com/xHggrX
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!