fork download
copy 
  1.     import java.util.*;
  2.     import java.io.*;
  3.     import java.math.*;
  4.     class smack {
  5.     	InputStream is;
  6.     	PrintWriter out;
  7.     	static long mod=pow(10,9)+7;
  8.     	static class Query implements Comparable<Query>
  9.     	{
  10.     		private int l,r,in,size,k;	
  11.     		public Query(int l, int r,int k,int in) 
  12.     		{ 
  13.     			this.l = l;
  14.     			this.r = r;
  15.     			this.in=in;
  16.     			this.k=k;
  17.     			this.size=l/block;
  18.     		}
  19.     		@Override
  20.     		public int compareTo(Query o) 
  21.     		{
  22.     			// TODO Auto-generated method stub
  23.     			if(this.size!=o.size)
  24.     				return this.size-o.size;
  25.     			else
  26.     				return this.r-o.r;
  27.     		}
  28.     	}
  29.     	static int block,freq[],above[];
  30.     	void solve()
  31.     	{
  32.     		int  t=1;
  33.     		while(t--!=0)
  34.     		{
  35.     			int n=ni();
  36.  
  37.     			int a[]=na(n);
  38.                 int q=ni();
  39.     			HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
  40.     			int temp[]=a.clone();
  41.     			Arrays.sort(temp);
  42.     			int count=0;
  43.     			hm.put(temp[0],++count);
  44.     			for(int i=1;i<n;i++)
  45.     			{
  46.     				if(temp[i]!=temp[i-1])
  47.     					hm.put(temp[i],++count);
  48.     			}
  49.     			for(int i=0;i<n;i++)
  50.     				a[i]=hm.get(a[i]);
  51.     			freq=new int[n+1];
  52.     			above=new int[n+1];
  53.     			block=(int)Math.sqrt(n);
  54.     			Query p[]=new Query[q];
  55.     			for(int i=0;i<q;i++)
  56.     				p[i]=new Query(ni()-1,ni()-1,1,i);
  57.     			Arrays.sort(p);
  58.     			int ans[]=new int[q];
  59.     			int curl=0,curr=-1;
  60.     			for(int i=0;i<q;i++)
  61.     			{
  62.     				int l=p[i].l;
  63.     				int r=p[i].r;
  64.     				while(curr>r)
  65.     				{
  66.     					delete(a[curr]);
  67.     					curr--;
  68.     				}
  69.     				while(curr<r)
  70.     				{
  71.     					curr++;
  72.     					add(a[curr]);
  73.     				}
  74.     				while(curl<l)
  75.     				{
  76.     					delete(a[curl]);
  77.     					curl++;
  78.     				}
  79.     				while(curl>l)
  80.     				{
  81.     					curl--;
  82.     					add(a[curl]);
  83.     				}
  84.     				ans[p[i].in]=above[0]-above[p[i].k];
  85.     			}
  86.     			for(int i=0;i<q;i++)
  87.     				out.println(ans[i]);
  88.     		}
  89.     	}
  90.     	public static void delete(int n)
  91.     	{
  92.     		if(freq[n]!=0){
  93.     			freq[n]--;
  94.     			above[freq[n]]--;
  95.     		}
  96.     	}
  97.     	public static void add(int n)
  98.     	{
  99.     		above[freq[n]]++;
  100.     		freq[n]++;
  101.     	}
  102.     	static long d, x, y;
  103.     	void extendedEuclid(long A, long B) {
  104.     	    if(B == 0) {
  105.     	        d = A;
  106.     	        x = 1;
  107.     	        y = 0;
  108.     	    }
  109.     	    else {
  110.     	        extendedEuclid(B, A%B);
  111.     	        long temp = x;
  112.     	        x = y;
  113.     	        y = temp - (A/B)*y;
  114.     	    }
  115.     	}
  116.     	long modInverse(long A,long M) //A and M are coprime
  117.     	{
  118.     	    extendedEuclid(A,M);
  119.     	    return (x%M+M)%M;    //x may be negative
  120.     	}
  121.     	public static void mergeSort(int[] arr, int l ,int r){
  122.     		if((r-l)>=1){
  123.     			int mid = (l+r)/2;
  124.     			mergeSort(arr,l,mid);
  125.     			mergeSort(arr,mid+1,r);
  126.     			merge(arr,l,r,mid);
  127.     		}
  128.     	}
  129.     	public static void merge(int arr[], int l, int r, int mid){
  130.     		int n1 = (mid-l+1), n2 = (r-mid);
  131.     		int left[] = new int[n1];
  132.     		int right[] = new int[n2];
  133.     		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
  134.     		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
  135.     		int i =0, j =0, k = l;
  136.     		while(i<n1 && j<n2){
  137.     			if(left[i]>right[j]){
  138.     				arr[k++] = right[j++];
  139.     			}
  140.     			else{
  141.     				arr[k++] = left[i++];
  142.     			}
  143.     		}
  144.     		while(i<n1) arr[k++] = left[i++];
  145.     		while(j<n2) arr[k++] = right[j++];
  146.     	}
  147.     	public static void mergeSort(long[] arr, int l ,int r){
  148.     		if((r-l)>=1){
  149.     			int mid = (l+r)/2;
  150.     			mergeSort(arr,l,mid);
  151.     			mergeSort(arr,mid+1,r);
  152.     			merge(arr,l,r,mid);
  153.     		}
  154.     	}
  155.     	public static void merge(long arr[], int l, int r, int mid){
  156.     		int n1 = (mid-l+1), n2 = (r-mid);
  157.     		long left[] = new long[n1];
  158.     		long right[] = new long[n2];
  159.     		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
  160.     		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
  161.     		int i =0, j =0, k = l;
  162.     		while(i<n1 && j<n2){
  163.     			if(left[i]>right[j]){
  164.     				arr[k++] = right[j++];
  165.     			}
  166.     			else{
  167.     				arr[k++] = left[i++];
  168.     			}
  169.     		}
  170.     		while(i<n1) arr[k++] = left[i++];
  171.     		while(j<n2) arr[k++] = right[j++];
  172.     	}
  173.     	 static class Pair implements Comparable<Pair>{
  174.  
  175.     	       int x,y,k,i;
  176.  
  177.     		Pair (int x,int y){
  178.     			this.x=x;
  179.     			this.y=y;
  180.     		}
  181.  
  182.     		public int compareTo(Pair o) {
  183.     					return this.x-o.x;
  184.     		}
  185.  
  186.     	        public boolean equals(Object o) {
  187.     	            if (o instanceof Pair) {
  188.     	                Pair p = (Pair)o;
  189.     	                return p.x == x && p.y == y && p.k==k;
  190.     	            }
  191.     	            return false;
  192.     	        }
  193.  
  194.  
  195.     	        @Override
  196.     	        public String toString() {
  197.     	            return  "("+x + " " + y +" "+k+" "+i+" )";
  198.     	        }
  199.  
  200.     	    } 
  201.  
  202.     	    public static boolean isPal(String s){
  203.     	        for(int i=0, j=s.length()-1;i<=j;i++,j--){
  204.     	                if(s.charAt(i)!=s.charAt(j)) return false;
  205.     	        }
  206.     	        return true;
  207.     	    }
  208.     	    public static String rev(String s){
  209.     			StringBuilder sb=new StringBuilder(s);
  210.     			sb.reverse();
  211.     			return sb.toString();
  212.     	    }
  213.  
  214.     	    public static long gcd(long x,long y){
  215.     		if(x%y==0)
  216.     			return y;
  217.     		else
  218.     			return gcd(y,x%y);
  219.     	    }
  220.  
  221.     	    public static int gcd(int x,int y){
  222.     		if(x%y==0)
  223.     			return y;
  224.     		else 
  225.     			return gcd(y,x%y);
  226.     	    }
  227.  
  228.     	    public static long gcdExtended(long a,long b,long[] x){
  229.  
  230.     	        if(a==0){
  231.     	            x[0]=0;
  232.     	            x[1]=1;
  233.     	            return b;
  234.     	        }
  235.     	        long[] y=new long[2];
  236.     	        long gcd=gcdExtended(b%a, a, y);
  237.  
  238.     	        x[0]=y[1]-(b/a)*y[0];
  239.     	        x[1]=y[0];
  240.  
  241.     	        return gcd;
  242.     	    }
  243.  
  244.     	    public static int abs(int a,int b){
  245.     		return (int)Math.abs(a-b);
  246.     	    }
  247.  
  248.     	    public static long abs(long a,long b){
  249.     		return (long)Math.abs(a-b);
  250.     	    }
  251.  
  252.     	    public static int max(int a,int b){
  253.     		if(a>b)
  254.     			return a;
  255.     		else
  256.     			return b;
  257.     	    }
  258.  
  259.     	    public static int min(int a,int b){
  260.     		if(a>b)
  261.     			return b;
  262.     		else 
  263.     			return a;
  264.     	    }
  265.  
  266.     	    public static long max(long a,long b){
  267.     		if(a>b)
  268.     			return a;
  269.     		else
  270.     			return b;
  271.     	    }
  272.  
  273.     	    public static long min(long a,long b){
  274.     		if(a>b)
  275.     			return b;
  276.     		else 
  277.     			return a;
  278.     	    }
  279.  
  280.     	    public static long pow(long n,long p,long m){
  281.     		 long  result = 1;
  282.     		  if(p==0)
  283.     		    return 1;
  284.     		if (p==1)
  285.     		    return n;
  286.     		while(p!=0)
  287.     		{
  288.     		    if(p%2==1)
  289.     		        result *= n;
  290.     		    if(result>=m)
  291.     		    result%=m;
  292.     		    p >>=1;
  293.     		    n*=n;
  294.     		    if(n>=m)
  295.     		    n%=m;
  296.     		}
  297.     		return result;
  298.     	    }
  299.  
  300.     	    public static long pow(long n,long p){
  301.     		long  result = 1;
  302.     		  if(p==0)
  303.     		    return 1;
  304.     		if (p==1)
  305.     		    return n;
  306.     		while(p!=0)
  307.     		{
  308.     		    if(p%2==1)
  309.     		        result *= n;	    
  310.     		    p >>=1;
  311.     		    n*=n;	    
  312.     		}
  313.     		return result;
  314.     	    }
  315.     	    public static void debug(Object... o) {
  316.     			System.out.println(Arrays.deepToString(o));
  317.     		}
  318.     	    void run() throws Exception {
  319.     			is = System.in;
  320.     			out = new PrintWriter(System.out);
  321.     			solve();
  322.     			out.flush();
  323.     		}
  324.  
  325.     	    public static void main(String[] args) throws Exception {
  326.     			new Thread(null, new Runnable() {
  327.     				public void run() {
  328.     					try {
  329.     						new smack().run();
  330.     					} catch (Exception e) {
  331.     						e.printStackTrace();
  332.     					}
  333.     				}
  334.     			}, "1", 1 << 26).start();
  335.     		}
  336.     	    private byte[] inbuf = new byte[1024];
  337.     		public int lenbuf = 0, ptrbuf = 0;
  338.  
  339.     		private int readByte() {
  340.     			if (lenbuf == -1)
  341.     				throw new InputMismatchException();
  342.     			if (ptrbuf >= lenbuf) {
  343.     				ptrbuf = 0;
  344.     				try {
  345.     					lenbuf = is.read(inbuf);
  346.     				} catch (IOException e) {
  347.     					throw new InputMismatchException();
  348.     				}
  349.     				if (lenbuf <= 0)
  350.     					return -1;
  351.     			}
  352.     			return inbuf[ptrbuf++];
  353.     		}
  354.  
  355.     		private boolean isSpaceChar(int c) {
  356.     			return !(c >= 33 && c <= 126);
  357.     		}
  358.  
  359.     		private int skip() {
  360.     			int b;
  361.     			while ((b = readByte()) != -1 && isSpaceChar(b));
  362.     			return b;
  363.     		}
  364.  
  365.     		private double nd() {
  366.     			return Double.parseDouble(ns());
  367.     		}
  368.  
  369.     		private char nc() {
  370.     			return (char) skip();
  371.     		}
  372.  
  373.     		private String ns() {
  374.     			int b = skip();
  375.     			StringBuilder sb = new StringBuilder();
  376.     			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
  377.     				sb.appendCodePoint(b);
  378.     				b = readByte();
  379.     			}
  380.     			return sb.toString();
  381.     		}
  382.  
  383.     		private char[] ns(int n) {
  384.     			char[] buf = new char[n];
  385.     			int b = skip(), p = 0;
  386.     			while (p < n && !(isSpaceChar(b))) {
  387.     				buf[p++] = (char) b;
  388.     				b = readByte();
  389.     			}
  390.     			return n == p ? buf : Arrays.copyOf(buf, p);
  391.     		}
  392.  
  393.     		private char[][] nm(int n, int m) {
  394.     			char[][] map = new char[n][];
  395.     			for (int i = 0; i < n; i++)
  396.     				map[i] = ns(m);
  397.     			return map;
  398.     		}
  399.  
  400.     		private int[] na(int n) {
  401.     			int[] a = new int[n];
  402.     			for (int i = 0; i < n; i++)
  403.     				a[i] = ni();
  404.     			return a;
  405.     		}
  406.  
  407.     		private int ni() {
  408.     			int num = 0, b;
  409.     			boolean minus = false;
  410.     			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
  411.     				;
  412.     			if (b == '-') {
  413.     				minus = true;
  414.     				b = readByte();
  415.     			}
  416.  
  417.     			while (true) {
  418.     				if (b >= '0' && b <= '9') {
  419.     					num = num * 10 + (b - '0');
  420.     				} else {
  421.     					return minus ? -num : num;
  422.     				}
  423.     				b = readByte();
  424.     			}
  425.     		}
  426.  
  427.     		private long nl() {
  428.     			long num = 0;
  429.     			int b;
  430.     			boolean minus = false;
  431.     			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
  432.     				;
  433.     			if (b == '-') {
  434.     				minus = true;
  435.     				b = readByte();
  436.     			}
  437.  
  438.     			while (true) {
  439.     				if (b >= '0' && b <= '9') {
  440.     					num = num * 10 + (b - '0');
  441.     				} else {
  442.     					return minus ? -num : num;
  443.     				}
  444.     				b = readByte();
  445.     			}
  446.     		}
  447.  
  448.     }
Success #stdin #stdout #stderr 0.06s 28008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
java.util.InputMismatchException
	at smack.readByte(Main.java:341)
	at smack.ni(Main.java:410)
	at smack.solve(Main.java:38)
	at smack.run(Main.java:321)
	at smack$1.run(Main.java:329)
	at java.lang.Thread.run(Thread.java:745)
https://ideone.com/Ywmdnf
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!