「BZOJ2743」[HEOI2012]采花

Description

萧薰儿是古国的公主,平时的一大爱好是采花。

今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花。

花园足够大,容纳了nn朵花,花有cc种颜色(用整数1c1-c表示),且花是排成一排的,以便于公主采花。公主每次采花后会统计采到的花的颜色数,颜色数越多她会越高兴!同时,她有一癖好,她不允许最后自己采到的花中,某一颜色的花只有一朵。为此,公主每采一朵花,要么此前已采到此颜色的花,要么有相当正确的直觉告诉她,她必能再次采到此颜色的花。

由于时间关系,公主只能走过花园连续的一段进行采花,便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了mm个行程,然后一一向你询问公主能采到多少朵花(她知道你是编程高手,定能快速给出答案!),最后会选择令公主最高兴的行程(为了拿到更多奖金!)。

Input

第一行四个空格隔开的整数nncc以及mm。接下来一行nn个空格隔开的整数,每个数在[1,c][1,c]间,第ii个数表示第ii朵花的颜色。接下来mm行每行两个空格隔开的整数llr(1lrn)r(1\leq l\leq r\leq n),表示女仆安排的行程为公主经过第ll到第rr朵花进行采花。

Output

mm行,每行一个整数,第ii个数表示公主在女仆的第ii个行程中能采到的花的颜色数。

Sample Input

1
2
3
4
5
6
7
5 3 5
1 2 2 3 1
1 5
1 2
2 2
2 3
3 5

Sample Output

1
2
3
4
5
2
0
0
1
0

HINT

对于100%100\%的数据,1n106,cn,m1061 \leq n \leq 10^6,c \leq n,m \leq 10^6

Soluton

preaipre_{a_i}表示颜色为aia_i的位置前一个。
ppaipp_{a_i}表示颜色为aia_i的位置前一个的前一个。
[1,r][1,r]区间内,每走到一个位置ii,让ppaipp_{a_i}这个位置的ss11,让preaipre_{a_i}这个位置的ss11
当一个颜色对答案合法,当且仅当preai[l,r]pre_{a_i}\in [l,r]其中preaipre_{a_i}是最后一个颜色aia_i的前一个位置。

如果用主席树维护,会TLE+MLE。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 2e6 + 66;
int n, c, m;
int a[N], pre[N];
int pp[N];

int rt[N];
int ls[N * 30], rs[N * 30];
int tot, sum[N * 30];
void ins(int pre,int &o, int l, int r, int x, int v) {
o = ++tot;
sum[o] = sum[pre] + v;
ls[o] = ls[pre];
rs[o] = rs[pre];
if(l == r) return ;
int mid = (l + r) >> 1;
if(x <= mid) ins(ls[pre], ls[o], l, mid, x, v);
else ins(rs[pre], rs[o], mid + 1, r, x ,v);
}
int query(int o, int l, int r, int L, int R) {
if(!o) return 0;
if(l <= L && r >= R) return sum[o];
int mid = (L + R) >> 1;
if(r <= mid) return query(ls[o], l, r, L, mid);
if(l > mid) return query(rs[o], l, r, mid + 1, R);
return query(ls[o], l, r, L, mid) + query(rs[o], l, r, mid + 1, R);
}
int id[N], num;
int ct[N];
int main() {
n = read(), c = read(), m = read();
for(int i = 1; i <= n; ++i) {
a[i] = read();
++ct[a[i]];
if(pre[a[i]]) {
if(ct[a[i]] > 2) {
++num;
ins(rt[num - 1], rt[num], 1, n, pp[a[i]], -1);
}
++num;
ins(rt[num - 1], rt[num], 1, n, pre[a[i]], 1);
pp[a[i]] = pre[a[i]];
pre[a[i]] = i;
id[i] = num;
} else {
pp[a[i]] = 0;
pre[a[i]] = i;
id[i] = num;
}
}
for(int i = 1; i <= m; ++i) {
int l = read(), r = read();
writeln(query(rt[id[r]], l, r, 1, n));
}
return 0;
}

所以离线查询,然后按照rr排序,用树状数组维护。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 2e6 + 66;
int n, c, m;
int a[N], pre[N];
int pp[N];
int ct[N];

int sum[N];
void add(int x, int v) {
for(; x <= n; x += x & -x)
sum[x] += v;
}
int query(int x) {
int res = 0;
for(; x; x -= x & -x)
res += sum[x];
return res;
}
struct Q {
int l, r, i;
}q[N];
bool cmpr(Q _x, Q _y) {
return _x.r < _y.r;
}
int ans[N];
int main() {
n = read(), c = read(), m = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
for(int i = 1; i <= m; ++i) {
q[i].l = read(), q[i].r = read();
q[i].i = i;
}
sort(q + 1, q + 1 + m, cmpr);
int p = 1;
for(int i = 1; i <= n; ++i) {
++ct[a[i]];
if(pre[a[i]]) {
if(ct[a[i]] > 2)
add(pp[a[i]], -1);
add(pre[a[i]], 1);
pp[a[i]] = pre[a[i]];
pre[a[i]] = i;
} else {
pp[a[i]] = 0;
pre[a[i]] = i;
}
while(p <= m && q[p].r == i) {
ans[q[p].i] = query(q[p].r) - query(q[p].l - 1);
++p;
}
}
for(int i = 1; i <= m; ++i)
writeln(ans[i]);
return 0;
}