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