| 题目名称 | 421. [SDOI 2009] HH的项链 |
|---|---|
| 输入输出 | diff.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2010-04-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：408， 提交：989， 通过率：41.25% | ||||
 Ezoi_XY |
100 | 0.312 s | 11.35 MiB | C++ |
 TA |
100 | 0.359 s | 17.10 MiB | C++ |
|
TA |
100 | 0.364 s | 17.10 MiB | C++ |
|
TA |
100 | 0.365 s | 17.10 MiB | C++ |
|
TA |
100 | 0.367 s | 15.39 MiB | C++ |
|
TA |
100 | 0.368 s | 12.33 MiB | C++ |
|
TA |
100 | 0.430 s | 17.48 MiB | C++ |
 枫华丶夜幻 |
100 | 0.466 s | 11.35 MiB | C++ |
|
TA |
100 | 0.471 s | 15.57 MiB | C++ |
 new ioer |
100 | 0.494 s | 10.08 MiB | C++ |
| 本题关联比赛 | |||
| 山东省选（随意做） | |||
| 20160407 | |||
| SYOI 专题 4：分块（根号杂烩） | |||
| SYOI 专题 5：扫描线 | |||
| 关于 HH的项链 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
看注释
| ||||
|
第一道莫队
| ||||
|
莫队莫队莫队
 サイタマ
2017-11-09 23:48
34楼
| ||||
|
一开始T了，后来发现freopen文件名写错了，呵呵呵
 落痕
2017-11-03 17:21
33楼
| ||||
|
%%%%%%%%%TA 太强辣
 PSI
2017-09-18 16:02
32楼
| ||||
|
数组大小啊
| ||||
|
回复 @Hzoi_DK :
不明不白地WA了两次。。。 | ||||
|
自己打的第一发莫队
数组开小wa了一次 莫队大法吼！！！  ~玖湫~
2017-07-09 20:15
29楼
| ||||
|
裸分块跑了五秒。。。。
 | ||||
|
这题居然是离线处理。。。。
在线想半天想出了一个n*nlogn的。。从n*n进化了。。。。。  | ||||
@@@
Shirry
Hzoi_Mafia
Hzoi_QTY
HeHe【题目描述】
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。
HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
【输入格式】
第一行：一个整数 $N$，表示项链的长度。
第二行：$N$ 个整数，依次表示项链中贝壳的种类编号（编号为 $0$ 到 $1000000$ 之间的整数）。
第三行：一个整数 $M$，表示 HH 询问的个数。
接下来 $M$ 行：每行两个整数，$L$ 和 $R(1 \le L \le R \le N)$，表示询问的区间。
【输出格式】
$M$ 行，每行一个整数，依次表示询问对应的答案。
【样例输入】
6 1 2 3 4 3 5 3 1 2 3 5 2 6
【样例输出】
2 2 4
【数据范围】
对于 $20\%$ 的数据，$N \le 100,M \le 1000$；
对于 $40\%$ 的数据，$N \le 3000,M \le 200000$；
对于 $100\%$ 的数据，$N \le 50000,M \le 200000$。