fork download
copy 
  1. //In submission class declaration should be default not public
  2.  
  3. import java.util.*;
  4. import java.io.*;
  5.  
  6. class D_query{
  7.  
  8. 	private static InputStream stream;
  9. 	private static byte[] buf = new byte[1024];
  10. 	private static int curChar;
  11. 	private static int numChars;
  12. 	private static SpaceCharFilter filter;
  13. 	private static PrintWriter pw;
  14. 	private static int[] count = new int[1111111];
  15. 	private static int ans = 0;
  16. 	private static int a[];
  17.  
  18. 	private static class Query{
  19. 		int ind, l , r, an;
  20. 		Query(int a,int b,int c){
  21. 			ind = a;
  22. 			l = b;
  23. 			r = c;
  24. 			an = 0;
  25. 		}
  26. 	}
  27.  
  28. 	private static void add(int p){
  29. 		count[a[p]]++;
  30. 		if(count[a[p]] == 1)
  31. 			ans++;
  32. 	}
  33. 	private static void remove(int p){
  34. 		if(count[a[p]] > 0){
  35. 			count[a[p]]--;
  36. 			if(count[a[p]] == 0)
  37. 				ans--;
  38. 		}
  39. 	}
  40.  
  41. 	private static void soln(){
  42. 		int n = nextInt();
  43. 		a = nextIntArray(n);
  44. 		int q = nextInt();
  45. 		Query[] qu = new Query[q];
  46. 		for (int i=0; i<q; i++) {
  47. 			qu[i] = new Query(i,nextInt()-1,nextInt()-1);
  48. 		}
  49. 		Arrays.sort(qu,new Comparator<Query>(){
  50. 			public int compare(Query q1,Query q2){
  51. 				if((int)(q1.l/Math.sqrt(n)) == (int)(q2.l/Math.sqrt(n)))
  52. 					return q1.r - q2.r;
  53. 				else
  54. 					return (int)((int)q1.l/Math.sqrt(n) - (int)q2.l/Math.sqrt(n));
  55. 			}
  56. 		});
  57.  
  58. 		int curL = 0;
  59. 		int curR = qu[0].l;
  60. 		for (int i=0; i<q; i++) {
  61. //			System.out.println("asd " + i + " " + qu[i].l+ " " + qu[i].r);
  62. //			System.out.println("cur " + curL + " " + curR);
  63. 			while(curL < qu[i].l){
  64. 				remove(curL);
  65. 				curL++;
  66. 			}
  67. //			System.out.println("cur " + curL + " " + curR);
  68. //			System.out.println(Arrays.toString(count));
  69. 			while(curL > qu[i].l){
  70. 				add(curL-1);
  71. 				curL--;
  72. 			}
  73. //			System.out.println("cur " + curL + " " + curR);
  74. //			System.out.println(Arrays.toString(count));
  75. 			while(curR <= qu[i].r){
  76. 				add(curR);
  77. 				curR++;
  78. 			}
  79. //			System.out.println("cur " + curL + " " + curR);
  80. //			System.out.println(Arrays.toString(count));
  81. 			while(curR > qu[i].r+1){
  82. 				remove(curR-1);
  83. 				curR--;
  84. 			}
  85. //			System.out.println("cur " + curL + " " + curR);
  86. //			System.out.println(Arrays.toString(count));
  87. //			System.out.println(ans);
  88. 			qu[i].an = ans;
  89. 		}
  90.  
  91. 		Arrays.sort(qu,new Comparator<Query>(){
  92. 			public int compare(Query q1,Query q2){
  93. 				return q1.ind - q2.ind;
  94. 			}
  95. 		});
  96.  
  97. 		for (int i=0; i<q; i++) {
  98. 			pw.println(qu[i].an);
  99. 		}
  100.  
  101. 	}
  102.  
  103. 	public static void main(String[] args){
  104. 		InputReader(System.in);
  105. 		pw = new PrintWriter(System.out);
  106. 		soln();
  107. 		pw.close();
  108. 	}
  109.  
  110.  
  111. 	// To Get Input
  112. 	// Some Buffer Methods
  113.  
  114. 	public static void InputReader(InputStream stream1) {
  115. 		stream = stream1;
  116. 	}
  117.  
  118. 	private static boolean isWhitespace(int c) {
  119. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  120. 	}
  121.  
  122. 	private static boolean isEndOfLine(int c) {
  123. 		return c == '\n' || c == '\r' || c == -1;
  124. 	}
  125.  
  126. 	private static int read() {
  127. 		if (numChars == -1)
  128. 			throw new InputMismatchException();
  129. 		if (curChar >= numChars) {
  130. 			curChar = 0;
  131. 			try {
  132. 				numChars = stream.read(buf);
  133. 			} catch (IOException e) {
  134. 				throw new InputMismatchException();
  135. 			}
  136. 			if (numChars <= 0)
  137. 				return -1;
  138. 		}
  139. 		return buf[curChar++];
  140. 	}
  141.  
  142. 	private static int nextInt() {
  143. 		int c = read();
  144. 		while (isSpaceChar(c))
  145. 			c = read();
  146. 		int sgn = 1;
  147. 		if (c == '-') {
  148. 			sgn = -1;
  149. 			c = read();
  150. 		}
  151. 		int res = 0;
  152. 		do {
  153. 			if (c < '0' || c > '9')
  154. 				throw new InputMismatchException();
  155. 			res *= 10;
  156. 			res += c - '0';
  157. 			c = read();
  158. 		} while (!isSpaceChar(c));
  159. 		return res * sgn;
  160. 	}
  161.  
  162. 	private static long nextLong() {
  163. 		int c = read();
  164. 		while (isSpaceChar(c))
  165. 			c = read();
  166. 		int sgn = 1;
  167. 		if (c == '-') {
  168. 			sgn = -1;
  169. 			c = read();
  170. 		}
  171. 		long res = 0;
  172. 		do {
  173. 			if (c < '0' || c > '9')
  174. 				throw new InputMismatchException();
  175. 			res *= 10;
  176. 			res += c - '0';
  177. 			c = read();
  178. 		} while (!isSpaceChar(c));
  179. 		return res * sgn;
  180. 	}
  181.  
  182. 	private static String nextToken() {
  183. 		int c = read();
  184. 		while (isSpaceChar(c))
  185. 			c = read();
  186. 		StringBuilder res = new StringBuilder();
  187. 		do {
  188. 			res.appendCodePoint(c);
  189. 			c = read();
  190. 		} while (!isSpaceChar(c));
  191. 		return res.toString();
  192. 	}
  193.  
  194. 	private static String nextLine() {
  195. 		int c = read();
  196. 		while (isSpaceChar(c))
  197. 			c = read();
  198. 		StringBuilder res = new StringBuilder();
  199. 		do {
  200. 			res.appendCodePoint(c);
  201. 			c = read();
  202. 		} while (!isEndOfLine(c));
  203. 		return res.toString();
  204. 	}
  205.  
  206. 	private static int[] nextIntArray(int n) {
  207. 		int[] arr = new int[n];
  208. 		for (int i = 0; i < n; i++) {
  209. 			arr[i] = nextInt();
  210. 		}
  211. 		return arr;
  212. 	}
  213.  
  214. 	private static long[] nextLongArray(int n) {
  215. 		long[] arr = new long[n];
  216. 		for (int i = 0; i < n; i++) {
  217. 			arr[i] = nextLong();
  218. 		}
  219. 		return arr;
  220. 	}
  221.  
  222. 	private static void pArray(int[] arr){
  223. 		for (int i=0; i<arr.length; i++) {
  224. 			System.out.print(arr[i] + " ");
  225. 		}
  226. 		System.out.println();
  227. 		return;
  228. 	}
  229.  
  230. 	private static void pArray(long[] arr){
  231. 		for (int i=0; i<arr.length; i++) {
  232. 			System.out.print(arr[i] + " ");
  233. 		}
  234. 		System.out.println();
  235. 		return;		
  236. 	}
  237.  
  238. 	private static boolean isSpaceChar(int c) {
  239. 		if (filter != null)
  240. 			return filter.isSpaceChar(c);
  241. 		return isWhitespace(c);
  242. 	}
  243.  
  244. 	private interface SpaceCharFilter {
  245. 		public boolean isSpaceChar(int ch);
  246. 	}
  247.  
  248. }
  249.  
Success #stdin #stdout 0.13s 320576KB
comments (?)
stdin
copy 
9
1 2 3 4 1 2 5 2 1
7
1 4
2 8
3 9
8 9
5 9
5 5
2 3
stdout
copy 
4
5
5
2
3
1
2
https://ideone.com/kv6j17
language:
Java (12.0.1)
created:
7 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!