Competitive_Programming/src/Data_Structures/MosAlgorithm.java at master · pct960/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
packageData_Structures;
importjava.util.Arrays;

// https://www.hackerearth.com/notes/mos-algorithm/
// Solution of http://www.spoj.com/problems/DQUERY/en/
publicclassMosAlgorithm {

publicstaticclassQuery {
intindex;
inta;
intb;

publicQuery(inta, intb) {
this.a = a;
this.b = b;
 }
	}

staticintadd(int[] a, int[] cnt, inti) {
return ++cnt[a[i]] == 1 ? 1 : 0;
	}

staticintremove(int[] a, int[] cnt, inti) {
return --cnt[a[i]] == 0 ? -1 : 0;
	}

publicstaticint[] processQueries(int[] a, Query[] queries) {
for (inti = 0; i < queries.length; i++) queries[i].index = i;
intsqrtn = (int) Math.sqrt(a.length);
Arrays.sort(queries, (q1, q2) -> {
intcmp = Integer.compare(q1.a / sqrtn, q2.a / sqrtn);
returncmp != 0 ? cmp : Integer.compare(q1.b, q2.b);
 });
int[] cnt = newint[1000_002];
int[] res = newint[queries.length];
intL = 1;
intR = 0;
intcur = 0;
for (Queryquery : queries) {
while (L < query.a) cur += remove(a, cnt, L++);
while (L > query.a) cur += add(a, cnt, --L);
while (R < query.b) cur += add(a, cnt, ++R);
while (R > query.b) cur += remove(a, cnt, R--);
res[query.index] = cur;
 }
returnres;
	}

publicstaticvoidmain(String[] args) {
int[] a = {1, 3, 3, 4};
Query[] queries = {newQuery(0, 3), newQuery(1, 3), newQuery(2, 3), newQuery(3, 3)};
int[] res = processQueries(a, queries);
System.out.println(Arrays.toString(res));
	}
}