洛谷 P1972 [SDOI2009]HH的项链

题目描述

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

输入输出格式

输入格式:

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

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

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

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

输出格式:

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

输入输出样例

输入样例#1:
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出样例#1:
2
2
4

说明

数据范围:

对于100%的数据,N <= 50000,M <= 200000。

分析

这题开始本来是打算用玄学线段树染色过的
然而,贝壳编号数与n的差距,显然是过不了的

这里用的是离线做法
记录pre与now两个数值,pre[i]指i点向后最近的与它编号相同的,now[c]指c编号贝壳的最前一个(有点像链式前向星)
然后以查询左边界排序 维护查询区间内存在唯一单种编号
查询自然是用树状数组


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
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l,r;
int id;
}ask[404040];
int n,m;
int a[101010],s[101010],ans[404040];
int now[1010101],pre[101010];

inline void read(int &x)
{
int data=0,w=1;
char ch=0;
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') w=-1,ch=getchar();
while (ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}

bool cmp(node u,node w)
{
return u.l<w.l || (u.l==w.r && u.r<w.r);
}

int bitset(int x)
{
return x&-x;
}

void add(int x)
{
while (x<=n)
{
++s[x];
x+=bitset(x);
}
}

int find(int x)
{
int ans=0;
while (x)
{
ans+=s[x];
x-=bitset(x);
}
return ans;
}

int main()
{
read(n);
for (int i=1;i<=n;++i)
read(a[i]);

for (int i=n;i>=1;--i)
{
pre[i]=now[a[i]];
now[a[i]]=i;
}
for (int i=1;i<=n;++i)
if (now[a[i]]==i)
add(i);

read(m);
for (int i=1;i<=m;++i)
{
read(ask[i].l);
read(ask[i].r);
ask[i].id=i;
}
sort(ask+1,ask+1+m,cmp);

int now=1,x,y;
for (int i=1;i<=m;++i)
{
while (now<ask[i].l)
{
if (pre[now]) add(pre[now]);
++now;
}
if (ask[i].l!=ask[i-1].l)
x=find(ask[i].l-1);
y=find(ask[i].r);
ans[ask[i].id]=y-x;
}
for (int i=1;i<=m;++i)
printf("%d\n",ans[i]);

return 0;
}
--------------------------
Hexo 强力驱动
主题 - NexT.Pisces