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