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