FilesExpand file tree

 master

/

DQUERY.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

85 lines (73 loc) · 1.37 KB

 master

/

DQUERY.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

85 lines (73 loc) · 1.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

/*

By Anudeep Nekkanti

Editorial at http://blog.anudeep2011.com/mos-algorithm/

Question at http://www.spoj.com/problems/DQUERY/

O( (N+M) * sqrt N )

*/

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 311111

#define A 1111111

#define BLOCK 555 // ~sqrt(N)

int cnt[A], a[N], ans[N], answer = 0;

struct node {

int L, R, i;

}q[N];

bool cmp(node x, node y) {

if(x.L/BLOCK != y.L/BLOCK) {

// different blocks, so sort by block.

return x.L/BLOCK < y.L/BLOCK;

}

// same block, so sort by R value

return x.R < y.R;

}

void add(int position) {

cnt[a[position]]++;

if(cnt[a[position]] == 1) {

answer++;

}

}

void remove(int position) {

cnt[a[position]]--;

if(cnt[a[position]] == 0) {

answer--;

}

}

int main() {

int n;

scanf("%d", &n);

for(int i=0; i<n; i++)

scanf("%d", &a[i]);

int m;

scanf("%d", &m);

for(int i=0; i<m; i++) {

scanf("%d%d", &q[i].L, &q[i].R);

q[i].L--; q[i].R--;

q[i].i = i;

}

sort(q, q + m, cmp);

int currentL = 0, currentR = 0;

for(int i=0; i<m; i++) {

int L = q[i].L, R = q[i].R;

while(currentL < L) {

remove(currentL);

currentL++;

}

while(currentL > L) {

add(currentL-1);

currentL--;

}

while(currentR <= R) {

add(currentR);

currentR++;

}

while(currentR > R+1) {

remove(currentR-1);

currentR--;

}

ans[q[i].i] = answer;

}

for(int i=0; i<m; i++)

printf("%d\n", ans[i]);

}