P3703HH的项链 时间限制 : - MS 空间限制 : 65536 KB 评测说明 : 时限1000ms 问题描述
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。 HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解 决这个问题。输入格式
第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。输出格式
M行，每行一个整数，依次表示询问对应的答案。样例输入
6 1 2 3 4 3 5 3 1 2 3 5 2 6样例输出
2 2 4提示
对于20%的数据，N ≤ 100，M ≤ 1000； 对于40%的数据，N ≤ 3000，M ≤ 200000； 对于100%的数据，N ≤ 50000，M ≤ 200000。来源 SDOI2009
这道题目虽然很难想，但是如果有足够的时间，一些简单的结论应该是能得出来的 首先先解释在线和离线
在线解法:存在多组数据，求多个解时，每输入一组数据就求出一个解 要求在于前后的解之间没有相互的影响 离线解法:存在多组数据，求多个解时，先读取全部数据，全部进行计算之后统一输出 一般用于前后数据相互干扰，单独求解会互相影响的题目所以这道题目，在线解法几乎不可能，因为前后求解的区间是可以有交集的，同时这个交集随着求解区间的不同而改变（这句话听不懂没关系） 所以我们选择离线解法，统一读取数据之后，进行有规律有目的性地求解
这道题目的数据最大的干扰在于，它们之间存在交集 使用树状数组时，求[l1,r1]和求[l2,r2]的区间如果存在交集，那么交集内的数字是不会改变的 那么，如果先求[l2,r2]，而交集内某些数字是在[l1,r1]的补集中出现过的，结果就会出现错误 （我知道你们看不懂，所以举个例子） 例如
项链 1 2 1 2 1 求[3,5]和[1,3]内不同元素的个数 先求[3,5]，我们就会在首先出现的不同元素上做标记 于是 项链 1 2 1 2 1 标记 1 1 那么用sum()求和，得到2，正解 但是，再求[1,3]时 项链 1 2 1 2 1 标记 1 1 1 1 用sum()求[1,3]的和，你会发现多了个1 这个时候就产生了冲突 这也是在线解题的冲突之处于是，为了解决这种冲突，我们就需要从前到后进行求解 那么有
先求[1,3] 于是 项链 1 2 1 2 1 标记 1 2 那么用sum()求和，得到2，正解 再求[2,5]时 项链 1 2 1 2 1 标记 1 1 1 用sum()求[2,5]的和,得到正解为2所以我们要先进行排序，以每个求解区间的起点为标准 具体做法
先使用结构体存区间 然后排序 得到起点从小到大的区间排序 （此处起点相通，终点乱序也可以）通过上述数据处理我们已经可以得出基本的解法了 就是
挨个找区间，并保证区间内所有数字的标记都是最大且唯一的（也就是说，没有两个相同的数字在一个区间被处理时同时被标记） 然后通过sum求这个区间的内标记总数排序之后我们已经能够保证区间之间没有冲突，但是我们的标记肯定是每读取一个区间更新一次 用暴力枚举肯定可行，但是会超时 此处需要用到一个快速确定数字的标记更新的方法
我们回顾一下图论当中的两种存图方式和各自的读图方式
一种是二维数组存入 这种存图方式在读图时是通过暴力枚举，遇到有标记为1的边时开始处理 这就对应了上述的暴力方法，当满足区间内某个数字没有被标记过时，我们就标记它 当然这种方法时完全不可取的
第二种存图方式就是存边 通过只存入有标记的边，来达到高效读图的目的 每一次读取都必定读到一个标记或者结束点
那么既然暴力解题的方式能够对应第一种存图方式，我们也可以将它改进成第二种
我们模仿存边的过程 对于一个数字，我们存入它第一次出现的点的坐标，以及每一个坐标对应的下一个坐标 例如
链子 1 2 3 1 2 3 1 2 3 我们存1出现的点 分为两部分，起点START[1]坐标为1，同时增加一个NEXT标记 得到结果 链子 1 2 3 1 2 3 1 2 3 NEXT 4 7 0 START[1]=1 第一个点对应的下个为1的点的坐标为4 同理得NEXT[4]=7 而NEXT[7]=0则表示没有下一个为1的点了 所以放出完整结果就是 START[1]=1;START[2]=2;START[3]=3; 链子 1 2 3 1 2 3 1 2 3 NEXT 4 5 6 7 8 9 0 0 0于是我们就得到了第一步，处理出START数组和NEXT数组（具体处理方法稍后解释）
那么得到上述标记之后，我们如何更新呢？？ 先举例
链子1 2 2 1 2 2 1 2 2 标记1 1 此时我们要求[3,6]的标记 由于坐标为1和2的点不在该区间当中，所以我们选择更新这两个点上数字的标记，使它在坐标为3的点后 那么NEXT[1]=4，我们更新坐标为4的点的坐标 链子1 2 2 1 2 2 1 2 2 标记1 1 1 此时，我们保证了区间左坐标之后第一个1被标记了，目的达到 那么我们处理下一个坐标上的数 NEXT[2]=3 链子1 2 2 1 2 2 1 2 2 标记1 1 1 1 这时坐标3之后的第一个2没有被标记 但是我们不急，更新下一个点，也就是我们刚更新的点 NEXT[3]=5 链子1 2 2 1 2 2 1 2 2 标记1 1 1 1 1 此时，坐标3之后的第一个3就被标记到了也就是说，我们的更新，实际过程是遍历区间左端点之前的点，并标记它的NEXT
这样子做，我们就能保证原本只在左端点之前被标记的数字一定在左端点之后被标记过，且被标记的点一定距离左端点最近（也就是上面过程的第一步到第二步）
如果更新之后某个数字的标记没有更新到左端点之后，不必慌张，因为我们是遍历更新的，所以当它被更新到左端点之前时，它一定会被再次更新（也就是上面过程的第三第四步）
这时，我们就需要一个更新进度点来记录此时已经更新到了哪个点 这样，下次更新时，我们就只需要从这个点更新到下一个区间的左端点即可 于是，更新的次数就保证不超过n次
顺便讲一下，最开始的标记是由START标记的，因为START表示的就是每个数字的第一个位置
只要用树状数组求到[l,r]的标记之和即可
不难发现，存边时，越是早存入的点在NEXT当中出现得就越晚 我们希望越早出现的点越早出现在NEXT当中，就反向读取项链
每读取一个数字，就更新START，然后把原本的START更新为NEXT 例如
1 1 1 从最后开始读取，读到坐标为3的点的数字为1->START[1]=3 坐标为2的点数字为1->NEXT[2]=START[1]=3,START[1]=2 坐标为1的点数字为1->NEXT[1]=START[1]=2,START[1]=1