BZOJ1878 - Click Here
Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
Input
第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
N ≤ 50000，M ≤ 200000
Output
M行，每行一个整数，依次表示询问对应的答案。
Solutions
注意到，如果知道[L,R]的数量情况，能够在$O(1)$的时间内得到[L-1,R]，[L+1,R]，[L,R-1]，[L,R+1]的数量情况。因此可以用莫队算法解决。
对于该题而言，$O(N \sqrt{N})$的时间显然是有些紧的。该题还可以用主席树解决。
由于每个区间询问中，一个数字只会被考虑一次，因此不妨认为只有第一次出现的数字对答案有贡献。
用last[i]记录第i位的数字上次出现位置。对于一个[L,R]的询问，答案即为[L,R]区间内last[i]<L的个数。跑一遍主席树即可。
CODE
CODE1(莫队算法) - Click Here
CODE2(主席树) - Click Here