【-42】P1972 [SDOI2009]HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数 $N$ ,表示项链的长度。

第二行:$N$ 个整数,表示依次表示项链中贝壳的编号(编号为$0$ 到$1000000$ 之间的整数)。

第三行:一个整数$M$,表示HH 询问的个数。

接下来$M$ 行:每行两个整数,L 和R($1 ≤ L ≤ R ≤ N$),表示询问的区间。

输出格式:

$M$ 行,每行一个整数,依次表示询问对应的答案。

输入输出样例

输入样例#1:

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

输出样例#1:

1
2
3
2
2
4

说明

数据范围:

对于 $100$% 的数据,$N \le 50000$,$M \le 200000$。

题解

开始写了一个线段树 然而和暴力没有半毛钱区别

(一下的颜色,相当于不同种类的贝壳)

然后搞了一种wa的方法,就是如果当前扫的位置已经到了某个颜色第一次出现的位置,那么就更新+1,如果已经过了某个颜色最后一次出现的位置,那么就更新,该颜色$-1$,然而发现如果在0~y这个区间段出现了这个颜色,并且x~y之间没有出现这个颜色,并且y之后出现了这种颜色,就会wa.

然后换了一种方法.

先离散

求出每个颜色第一次出现的位置,加入到树状数组中.

求出每个位置,该颜色在其后面第一次出现的位置.记录,为$ne$数组

然后每次询问左端点排序.

把询问左端点左边的点i的 $ne[i]$加入树状数组中(这样并不会算重,想一想为什么)

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
int n,p1;
struct node
{
int d;
int id;
}
a[50010];
int ne[50010];
int po[50010];
struct node1
{
int x,y;
int id;
} b[200010];
int Ans[200010];
int a1[50010];
node first[50010];
int last[50010];
int flag[50010];
int t[70000];
int b1,b2,m;
bool cmp(node aa,node bb)
{
return aa.d<bb.d;
}
bool cmp1(node1 aa,node1 bb)
{
if (aa.x==bb.x) return aa.y<bb.y;
return aa.x<bb.x;
}
void xg(int x,int p3)
{
while (x<=n+1)
{
//cout<<x;
t[x]+=p3;
x+=(x&-x);
}
}
int qh(int x)
{
int ans=0;
while (x)
{
ans+=t[x];
x-=(x&-x);
}
return ans;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i].d=read(),a[i].id=i;//记录颜色,标号
sort(a+1,a+n+1,cmp);//按照颜色排序
p1=0;
a[0].d=-2333;//标记
for (int i=1;i<=n;i++)
{
if (a[i].d!=a[i-1].d) p1++;
a1[a[i].id]=p1;
}//离散
for (int i=1;i<=n;i++)
{
if (!flag[a1[i]])
{
flag[a1[i]]=1;
xg(i,1);//该颜色第一次出现的位置
first[a1[i]].d=i;
first[a1[i]].id=a1[i];
}
}//找每个颜色第一次出现的位置
for (int i=n;i>=1;i--)
{
ne[i]=last[a1[i]];
last[a1[i]]=i;
}//求出i位置以后,i位置的颜色x下一次出现的位置
b1=0;b2=0;
sort(first+1,first+p1+1,cmp);//按照时间顺序排序
m=read();
for (int i=1;i<=m;i++)
{
b[i].id=i;
b[i].x=read();b[i].y=read();
}
sort(b+1,b+m+1,cmp1);//按照左端点排序
b1=1;
for (int i=1;i<=m;i++)
{
if (b[i].y<b[i].x)//特判
{
Ans[b[i].id]=0;
continue;
}
while (b1<b[i].x)//修改
{
if (ne[b1]!=0)
{
//printf("(b1:%d,ne,%d)",b1,ne[b1]);
xg(ne[b1],1);
}
b1++;
}
Ans[b[i].id]=qh(b[i].y)-qh(b[i].x-1);//求解
}
//printf("\n");
for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);
}