• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Dec 19th, 2016 161 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2. import java.io.IOException;
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.
21.         int n,m;
22.         String[]s;
24.
26.         for (int i = 0; i < n; i++) {
27.             a[i]=Integer.parseInt(s[i]);
28.         }
30.
31.         //Input queries
32.         for (int i = 0; i < m; i++) {
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){
65.                // System.out.println("add called from l--");
66.
67.                 currentL--;
68.             }
69.
70.             while (currentR<=queries[i].r){
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.
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)
98.     }
99.
100.     private static void remove(int pos) {
101.         count[a[pos]]--;
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.

Top