Description:


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

Input:


第一行:一个整数N,表示项链的长度。 第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。 第三行:一个整数M,表示HH询问的个数。 接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

Output:


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

Sample Input:


Sample Output:


题解:


貌似这一题捉法很多,在线可以直接上主席树,离线可以上莫队和树状数组。

我是用树状数组来捉的,方法很奇特。
首先对于每一种贝壳第一次出现的位置x,b[x]++。
然后将询问按左端点排序,然后从左往右扫每一个贝壳。
对于每一个贝壳x,b[next[a[x]]]++,next[a[x]]表示下一个和x种类相同的贝壳的位置。
用树状数组处理b数组,遇到询问左端点时用Query(r)-Query(l-1)更新答案。
这样巧妙地避免了每一个询问中同种贝壳算两次。

莫队算法见汪叔叔的博客->戳这里

树状数组做法如下: