BZOJ1878 | SDOI2009 HH的项链

题目描述

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

输入输出格式

输入格式:

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

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

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

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

输出格式:

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

什么描述啊……

我们可以 简单地 发现对于每次区间询问,如果一种编号出现了多次,那么只有最后一次才是有意义的。

那么离线询问并按照R为第一关键字,L为第二关键字排序。

然后从当前位置指针(初始为1,当然)扫到R统计有没有新出现的和重复出现的

如果是新出现的那么标记一下再扔到树状数组里(哦,忘记了,树状数组是按位置建的,也就是下标和项链是对应的)

如果是重复出现的,那么,有一个数组保存之前出现的位置,get到这个位置然后往树状数组里这个位置扔一个-1就行了。

之后更新前一次出现位置数组并扔进树状数组里。

最后求区间和……

真是一道好题。