Bzoj 1878(莫队)

BZOJ 1878
此处讲解,莫队入门题

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
const int MAXN = 1000000 + 5;
int m, n, totblo, ai[MAXN], bl[MAXN];
struct query {
int l, r, id, ans;//询问左边界,右边界,第几个询问,答案
}q[MAXN];
bool cmp1(const query &a, const query &b) {//莫队排序
if (bl[a.l] == bl[b.l]) return a.r < b.r;
return bl[a.l] < bl[b.l];
}
bool cmp2(const query &a, const query &b) {
return a.id < b.id;
}
int nl, nr, nans, tax[MAXN];//当前l位置,当前r位置,当前答案,桶
void clean() {nl = nr = nans = 0, ms(tax, 0);}
void adjust(int x, int add) {
if (tax[ai[x]] == 0 && add == 1) nans++;
tax[ai[x]] += add;
if (tax[ai[x]] == 0 && add == -1) nans--;
/*一定要指明add
否则 对于询问区间1 3后询问5 8 会炸
*/
}
int solve() {
clean();
totblo = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &ai[i]);
bl[i] = (i - 1) / totblo + 1;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp1);
nl = 1, nr = 0;
for (int i = 1; i <= m; i++) {
while (nl < q[i].l) adjust(nl , -1), nl++;
while (nl > q[i].l) adjust(nl - 1, +1), nl--;
while (nr < q[i].r) adjust(nr + 1, +1), nr++;
while (nr > q[i].r) adjust(nr , -1), nr--;
q[i].ans = nans;//进行调整
}
sort(q + 1, q + 1 + m, cmp2);
for (int i = 1; i <= m; i++) printf("%d\n", q[i].ans);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------