fork(2) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. class MKTHNUM{
  4. 	static int n;
  5. 	static int [][]a;
  6. 	static int [][]st;
  7. 	public static void main(String []arg) throws IOException{
  8. 		InputReader in = new InputReader(System.in);
  9.         OutputWriter out = new OutputWriter(System.out);
  10. 		n = in.readInt();
  11. 		int m = in.readInt();
  12. 		int []tmp = new int[n];
  13. 		a = new int[n][2];
  14. 		for(int i=0;i<n;i++){
  15. 			a[i][0] = in.readInt();
  16. 			tmp[i] = a[i][0];
  17. 			a[i][1] = i;
  18. 		}
  19. 		mergeSort(0,n-1);
  20. 		st = new int[263005][];
  21. 		constructST(0,n-1,0);
  22. 		while(m-- > 0){
  23. 			int l = in.readInt()-1; 
  24. 			int r = in.readInt()-1;
  25. 			int k = in.readInt();
  26. 			out.printLine(tmp[query(0,n-1,l,r,0,k)]);
  27. 			out.flush();
  28. 		}
  29. 		out.close();
  30. 	}
  31.  
  32. 	static void constructST(int s, int e,int i){
  33. 		if(e < s){
  34. 			return ;
  35. 		}
  36. 		if(e == s){
  37. 			st[i] = new int[1];
  38. 			st[i][0] = a[e][1];
  39. 			return ;
  40. 		}
  41. 		int mid = s + (e-s)/2;
  42. 		constructST(s,mid,2*i+1);
  43. 		constructST(mid+1,e,2*i+2);
  44. 		mergeST(i);
  45. 	}
  46.  
  47. 	static int query(int s,int e,int qs,int qe,int i,int k){
  48. 		if(s == e){
  49. 			return st[i][0];
  50. 		}
  51. 		int upperBound = binarySearch(0,st[2*i+1].length,st[2*i+1],qe);
  52. 		int lowerBound = binarySearch(0,st[2*i+1].length,st[2*i+1],qs-1);
  53. 		int mid = s + (e-s)/2;
  54. 		if(upperBound - lowerBound >= k){
  55. 			return query(s,mid,qs,qe,2*i+1,k);
  56. 		}else{
  57. 			return query(mid+1,e,qs,qe,2*i+2,(k - (upperBound-lowerBound)));
  58. 		}
  59. 	}
  60.  
  61. 	static int binarySearch(int s,int e,int []arr,int val){
  62. 		if(s < e){
  63. 			int mid = s + (e-s)/2;
  64. 			if(val >= arr[mid]){
  65. 				return binarySearch(mid+1,e,arr,val);
  66. 			}else{
  67. 				return binarySearch(s,mid,arr,val);
  68. 			}
  69. 		}
  70. 		return s;
  71. 	}
  72.  
  73. 	static void mergeSort(int s,int e){
  74. 		if(s < e){
  75. 			int mid = s + (e-s)/2;
  76. 			mergeSort(s,mid);
  77. 			mergeSort(mid+1,e);
  78. 			merge(s,mid,e);
  79. 		}
  80. 	}
  81.  
  82. 	static void merge(int s,int mid,int e){
  83. 		int l1 = mid - s + 1;
  84. 		int l2 = e - mid;
  85. 		int [][]l = new int[l1][2];
  86. 		int [][]r = new int[l2][2];
  87. 		for(int i=0;i<l1;i++){
  88. 			l[i][0] = a[s+i][0];
  89. 			l[i][1] = a[s+i][1];
  90. 		}
  91. 		for(int i=0;i<l2;i++){
  92. 			r[i][0] = a[mid+i+1][0];
  93. 			r[i][1] = a[mid+i+1][1];
  94. 		}
  95. 		int i = 0;
  96. 		int j = 0;
  97. 		int k = s;
  98. 		while(i<l1 && j<l2){
  99. 			if(l[i][0] <= r[j][0]){
  100. 				a[k][0] = l[i][0];
  101. 				a[k++][1] = l[i++][1];
  102. 			}else{
  103. 				a[k][0] = r[j][0];
  104. 				a[k++][1] = r[j++][1];
  105. 			}
  106. 		}
  107. 		while(i<l1){
  108. 			a[k][0] = l[i][0];
  109. 			a[k++][1] = l[i++][1];
  110. 		}
  111. 		while(j<l2){
  112. 			a[k][0] = r[j][0];
  113. 			a[k++][1] = r[j++][1];
  114. 		}
  115. 	}
  116.  
  117. 	static void mergeST(int i){
  118. 		int left = 2*i+1;
  119. 		int right = 2*i+2;
  120. 		int l1 = st[left].length;
  121. 		int l2 = st[right].length;
  122. 		st[i] = new int[l1+l2];
  123. 		int a = 0;
  124. 		int b = 0;
  125. 		int c = 0;
  126. 		while(a<l1 && b<l2){
  127. 			if(st[left][a] <= st[right][b]){
  128. 				st[i][c++] = st[left][a++];
  129. 			}else{
  130. 				st[i][c++] = st[right][b++];
  131. 			}
  132. 		}
  133. 		while(a<l1){
  134. 			st[i][c++] = st[left][a++];
  135. 		}
  136. 		while(b<l2){
  137. 			st[i][c++] = st[right][b++];
  138. 		}
  139. 	}
  140.  
  141.  
  142.  
  143. 	//For Fast I/O
  144. 	private static class InputReader{
  145.         private InputStream stream;
  146.         private byte[] buf = new byte[1024];
  147.         private int curChar;
  148.         private int numChars;
  149.         private SpaceCharFilter filter;
  150.  
  151.         public InputReader(InputStream stream){
  152.             this.stream = stream;
  153.         }
  154.  
  155.         public int read(){
  156.             if (numChars == -1)
  157.                 throw new InputMismatchException();
  158.             if (curChar >= numChars){
  159.                 curChar = 0;
  160.                 try{
  161.                     numChars = stream.read(buf);
  162.                 } catch (IOException e){
  163.                     throw new InputMismatchException();
  164.                 }
  165.                 if (numChars <= 0)
  166.                     return -1;
  167.             }
  168.             return buf[curChar++];
  169.         }
  170.  
  171.         public int readInt(){
  172.             int c = read();
  173.             while (isSpaceChar(c))
  174.                 c = read();
  175.             int sgn = 1;
  176.             if (c == '-'){
  177.                 sgn = -1;
  178.                 c = read();
  179.             }
  180.             int res = 0;
  181.             do{
  182.                 if (c < '0' || c > '9')
  183.                     throw new InputMismatchException();
  184.                 res *= 10;
  185.                 res += c - '0';
  186.                 c = read();
  187.             } while (!isSpaceChar(c));
  188.             return res * sgn;
  189.         }
  190.  
  191.         public String readString(){
  192.             int c = read();
  193.             while (isSpaceChar(c))
  194.                 c = read();
  195.             StringBuilder res = new StringBuilder();
  196.             do{
  197.                 res.appendCodePoint(c);
  198.                 c = read();
  199.             } while (!isSpaceChar(c));
  200.             return res.toString();
  201.         }
  202.  
  203.         public boolean isSpaceChar(int c){
  204.             if (filter != null)
  205.                 return filter.isSpaceChar(c);
  206.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  207.         }
  208.  
  209.         public String next(){
  210.             return readString();
  211.         }
  212.  
  213.         public interface SpaceCharFilter{
  214.             public boolean isSpaceChar(int ch);
  215.         }
  216.     }
  217.  
  218.     private static class OutputWriter{
  219.         private final PrintWriter writer;
  220.  
  221.         public OutputWriter(OutputStream outputStream){
  222.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  223.         }
  224.  
  225.         public OutputWriter(Writer writer){
  226.             this.writer = new PrintWriter(writer);
  227.         }
  228.  
  229.         public void print(Object... objects){
  230.             for (int i = 0; i < objects.length; i++){
  231.                 if (i != 0)
  232.                     writer.print(' ');
  233.                 writer.print(objects[i]);
  234.             }
  235.         }
  236.  
  237.         public void printLine(Object... objects) {
  238.             print(objects);
  239.             writer.println();
  240.         }
  241.  
  242.         public void close(){
  243.             writer.close();
  244.         }
  245.  
  246.         public void flush(){
  247.             writer.flush();
  248.         }
  249.     }
  250. }
Success #stdin #stdout 0.05s 4386816KB
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/pHN7Z2
language:
Java (HotSpot 12)
created:
6 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!