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