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

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!