fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5.  
  6. class Query implements Comparable<Query>
  7. {
  8. 	int index;
  9. 	int left;
  10. 	int right;
  11.  
  12. 	public Query()
  13. 	{
  14. 		index = 0;
  15. 		left = 0;
  16. 		right = 0;
  17. 	}
  18. 	public int compareTo(Query q)
  19. 	{
  20. 		int left1 = this.left/dquery.blocksize;
  21. 		int left2 = q.left/dquery.blocksize;
  22.  
  23. 		if(left1-left2==0)
  24. 			return this.right-q.right;
  25. 		else
  26. 			return left1-left2;
  27. 	}
  28. }
  29.  
  30. class dquery
  31. {
  32. 	public static int blocksize = 0;
  33.     public static void main(String[] args) throws IOException
  34.     {
  35.  
  36. 		Reader obj =new Reader();
  37.         BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  38. 		int n = obj.nextInt();
  39. 		int[] arr = new int[n];
  40. 		for(int i=0;i<n;i++)
  41. 			arr[i] = obj.nextInt();
  42.  
  43. 		ArrayList<Query> list = new ArrayList<Query>();
  44. 		int nq = obj.nextInt();
  45.  
  46. 		for(int i=0;i<nq;i++)
  47. 		{
  48. 			Query qn = new Query();
  49. 			qn.index = i;
  50. 			qn.left = obj.nextInt()-1;
  51. 			qn.right = obj.nextInt()-1;
  52. 			list.add(qn);
  53. 		}
  54.  
  55. 		blocksize = (int)Math.sqrt(n);
  56. //		System.out.println("block size "+blocksize);
  57. 		Collections.sort(list);
  58.  
  59. 		int[] count = new int[(int)1e6+1];
  60. 		int[] answer = new int[nq];
  61.  
  62. 		int start = list.get(0).left;
  63. 		int end = start;
  64. 		count[arr[start]]++;
  65. 		int ans = 1;
  66. 		for(Query q:list)
  67. 		{
  68. 			while(start<q.left)
  69. 			{
  70. 				count[arr[start]]--;
  71. 				if(count[arr[start]]==0)
  72. 					ans--;
  73. 				start++;
  74. 			}
  75. 			while(start>q.left)
  76. 			{
  77. 				start--;
  78. 				count[arr[start]]++;
  79. 				if(count[arr[start]]==1)
  80. 					ans++;
  81. 			}
  82. 			while(end<q.right)
  83. 			{
  84. 				end++;
  85. 				count[arr[end]]++;
  86. 				if(count[arr[end]]==1)
  87. 					ans++;
  88. 			}
  89. 			while(end>q.right)
  90. 			{
  91. 				count[arr[end]]--;
  92. 				if(count[arr[end]]==0)
  93. 					ans--;
  94. 				end--;
  95. 			}
  96. 			answer[q.index] = ans;
  97. 		}
  98. 		for(int i=0;i<nq;i++)
  99. 			out.write(answer[i]+"\n");
  100. 		out.close();		
  101. 	}
  102.  
  103.     static class Reader
  104.     {
  105.         final private int BUFFER_SIZE = 1 << 16;
  106.         private DataInputStream din;
  107.         private byte[] buffer;
  108.         private int bufferPointer, bytesRead;
  109.  
  110.         public Reader()
  111.         {
  112.             din = new DataInputStream(System.in);
  113.             buffer = new byte[BUFFER_SIZE];
  114.             bufferPointer = bytesRead = 0;
  115.         }
  116.  
  117.         public Reader(String file_name) throws IOException
  118.         {
  119.             din = new DataInputStream(new FileInputStream(file_name));
  120.             buffer = new byte[BUFFER_SIZE];
  121.             bufferPointer = bytesRead = 0;
  122.         }
  123.  
  124.         public String readLine() throws IOException
  125.         {
  126.             byte[] buf = new byte[64]; // line length
  127.             int cnt = 0, c;
  128.             while ((c = read()) != -1)
  129.             {
  130.                 if (c == '\n')
  131.                     break;
  132.                 buf[cnt++] = (byte) c;
  133.             }
  134.             return new String(buf, 0, cnt);
  135.         }
  136.  
  137.         public int nextInt() throws IOException
  138.         {
  139.             int ret = 0;
  140.             byte c = read();
  141.             while (c <= ' ')
  142.                 c = read();
  143.             boolean neg = (c == '-');
  144.             if (neg)
  145.                 c = read();
  146.             do
  147.             {
  148.                 ret = ret * 10 + c - '0';
  149.             }  while ((c = read()) >= '0' && c <= '9');
  150.  
  151.             if (neg)
  152.                 return -ret;
  153.             return ret;
  154.         }
  155.  
  156.         public long nextLong() throws IOException
  157.         {
  158.             long ret = 0;
  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.             }
  168.             while ((c = read()) >= '0' && c <= '9');
  169.             if (neg)
  170.                 return -ret;
  171.             return ret;
  172.         }
  173.  
  174.         public double nextDouble() throws IOException
  175.         {
  176.             double ret = 0, div = 1;
  177.             byte c = read();
  178.             while (c <= ' ')
  179.                 c = read();
  180.             boolean neg = (c == '-');
  181.             if (neg)
  182.                 c = read();
  183.  
  184.             do {
  185.                 ret = ret * 10 + c - '0';
  186.             }
  187.             while ((c = read()) >= '0' && c <= '9');
  188.  
  189.             if (c == '.')
  190.             {
  191.                 while ((c = read()) >= '0' && c <= '9')
  192.                 {
  193.                     ret += (c - '0') / (div *= 10);
  194.                 }
  195.             }
  196.  
  197.             if (neg)
  198.                 return -ret;
  199.             return ret;
  200.         }
  201.  
  202.         private void fillBuffer() throws IOException
  203.         {
  204.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  205.             if (bytesRead == -1)
  206.                 buffer[0] = -1;
  207.         }
  208.  
  209.         private byte read() throws IOException
  210.         {
  211.             if (bufferPointer == bytesRead)
  212.                 fillBuffer();
  213.             return buffer[bufferPointer++];
  214.         }
  215.  
  216.         public void close() throws IOException
  217.         {
  218.             if (din == null)
  219.                 return;
  220.             din.close();
  221.         }
  222.     }
  223.  
  224. }
  225.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/1a3ATr
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!