SHARE
TWEET

Untitled

a guest Dec 19th, 2016 161 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. /**
  7.  * Created by arpit on 19/12/16.
  8.  */
  9. class MOSAlgorithm {
  10.  
  11.     static final int MAX=311111;
  12.     static Query[]queries=new Query[MAX];
  13.     static int[]a=new int[MAX];
  14.     static int[]count=new int[MAX];
  15.     static int ans[]=new int[MAX],answer =0;
  16.     static int blockSize;
  17.  
  18.     public static void main(String[] args) throws IOException {
  19.  
  20.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  21.         int n,m;
  22.         String[]s;
  23.         n=Integer.parseInt(br.readLine());
  24.  
  25.         s=br.readLine().split("\\s");//Input array
  26.         for (int i = 0; i < n; i++) {
  27.             a[i]=Integer.parseInt(s[i]);
  28.         }
  29.         m=Integer.parseInt(br.readLine());
  30.  
  31.         //Input queries
  32.         for (int i = 0; i < m; i++) {
  33.             s=br.readLine().split("\\s");
  34.             queries[i]=new Query(Integer.parseInt(s[0])-1,Integer.parseInt(s[1])-1,i);
  35.         }
  36.  
  37.         blockSize= (int) Math.sqrt(n);
  38.  
  39.         solve(n,m);
  40.  
  41.  
  42.     }
  43.  
  44.     private static void solve(int n, int m) {
  45.  
  46.         Arrays.sort(queries,0,m);
  47.  
  48.         /*for (int i = 0; i < m; i++) {
  49.             System.out.print(queries[i] + " ");
  50.         }
  51.         System.out.println();*/
  52.  
  53.         int currentL=0,currentR=0;
  54.  
  55.         for (int i = 0; i < m; i++) {
  56.  
  57.             while (currentL<queries[i].l){
  58.                 remove(currentL);
  59.               //  System.out.println("remove called from l++");
  60.                 currentL++;
  61.             }
  62.  
  63.             while (currentL>queries[i].l){
  64.                 add(currentL-1);
  65.                // System.out.println("add called from l--");
  66.  
  67.                 currentL--;
  68.             }
  69.  
  70.             while (currentR<=queries[i].r){
  71.                 add(currentR);
  72.                // System.out.println("add called from r++");
  73.  
  74.                 currentR++;
  75.             }
  76.             while (currentR>(queries[i].r+1)){
  77.                 remove(currentR-1);
  78.                // System.out.println("remove called from r--");
  79.  
  80.                 currentR--;
  81.             }
  82.  
  83.             ans[queries[i].i]=answer;
  84.  
  85.         }
  86.  
  87.         for (int i = 0; i < m; i++) {
  88.             System.out.println(ans[i]);
  89.         }
  90.  
  91.     }
  92.  
  93.     private static void add(int pos) {
  94.         int temp=a[pos];
  95.         count[temp]++;
  96.         if (count[a[pos]]==1)
  97.             answer++;
  98.     }
  99.  
  100.     private static void remove(int pos) {
  101.         count[a[pos]]--;
  102.         if (count[a[pos]]==0) answer--;
  103.     }
  104.  
  105.     static class Query implements Comparable<Query>{
  106.  
  107.         int l,r,i;
  108.  
  109.         public Query(int l, int r, int i) {
  110.             this.l = l;
  111.             this.r = r;
  112.             this.i = i;
  113.         }
  114.  
  115.         @Override
  116.         public int compareTo(Query query) {
  117.             if ((this.l/blockSize)!=(query.l/blockSize))
  118.                 return ((Integer) (this.l/blockSize)).compareTo(query.l/blockSize);
  119.  
  120.             return ((Integer)(this.r)).compareTo(query.r);
  121.         }
  122.  
  123.         @Override
  124.         public String toString() {
  125.             return "Query{" +
  126.                     "l=" + l +
  127.                     ", r=" + r +
  128.                     ", i=" + i +
  129.                     '}';
  130.         }
  131.     }
  132. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top