Problem’s Website
- [SDOI2009]HH的项链
Solution
- 首先这道题模拟是不可能AC的。
- 其次这道题可以用莫队AC，但我不会。
- 我们来说一下比较大众化的做法，离线处理+树状数组，我们可以先按照询问区间的右端点升序排序，然后用一个数组存一个元素在一个区间中出现的位置，用树状数组记录区间内的元素个数。
Code
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
using namespace std;
int sc() {
int xx = 0, ff = 1; char cch = gc;
while(cch < '0' || cch > '9') {
if(cch == '-') ff = -1; cch = gc;
}
while(cch >= '0' && cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
struct node {
int l, r, id;
bool operator < (const node &x) const {
return r < x.r;
}
}b[500010];
int n, m;
int a[500010], ans[500010], tree[1000010], place[1000010];
int lowbit(int x) {
return x & (-x);
}
void update(int id, int num) {
while(id <= n) {
tree[id] += num;
id += lowbit(id);
}
}
int query(int id) {
int sum = 0;
while(id > 0) {
sum += tree[id];
id -= lowbit(id);
}
return sum;
}
int main() {
n = sc();
for(int i = 1; i <= n; i++)
a[i] = sc();
m = sc();
for(int i = 1; i <= m; i++) {
b[i].l = sc();
b[i].r = sc();
b[i].id = i;
}
sort(b + 1, b + 1 + m);
int next = 1;
for(int i = 1; i <= m; i++) {
for(int j = next; j <= b[i].r; j++) {
if(place[a[j]])
update(place[a[j]], -1);
update(j, 1);
place[a[j]] = j;
}
next = b[i].r + 1;
ans[b[i].id] = query(b[i].r) - query(b[i].l - 1);
}
for(int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
rp++