Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一

段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一

个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只

好求助睿智的你，来解决这个问题。

Input

第一行：一个整数 \(N\)，表示项链的长度。

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

第三行：一个整数 \(M\)，表示HH询问的个数。

接下来 \(M\) 行：每行两个整数，\(L\) 和 \(R\)（\(1 ≤ L ≤ R ≤ N\)），表示询问的区间。

\(N ≤ 50000\)，\(M ≤ 200000\)。

Output

\(M\) 行，每行一个整数，依次表示询问对应的答案。

---

Soulution:

SOL_1

离线处理，可以将问题进行转化。

先按照询问的右端点排序，于是我们可以对每个右端点依次回答以下问题：

从序列中一个位置到最后，有多少种颜色

这时，我们可以将该段原序列的前缀（即从头到固定的右端点）中每种颜色最后的位置赋为 \(1\) ，该颜色之前出现的位置赋为 \(0\) ，计算前缀和 \(sum(r)\) 以及 \(sum(l-1)\) ，相减就是出现的颜色数，用树状数组维护即可。

具体操作：

1.按右端点排序

2.对于当前所到点 \(i\) 用树状数组将 \(i\) 处加 \(1\) ，在 \(next[i]\) (前一个出现位置)处减 \(1\)

3.回答所有右端点与 \(i\) 相同的询问

总复杂度 \(O(nlogn)\)

#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN = 200000+9;const int SIZE = 1000000+9;int tree[MAXN];int head[SIZE];int next[MAXN];int num[MAXN];int n,m;struct Q{    int l,r,id,val;}ask[MAXN];bool cmp(const Q &A,const Q &B){    return A.r==B.r?A.l
       
      
     
    

SOL_2

在线算法

使用主席树，计算当前询问区间 \([L,R]\) 有多少点的 \(pred\) （同样是前一次出现的位置） 要小于 \(L\) 这就是最终的答案。

感觉这个不用怎么解释，这样做可以计算颜色并且不重复，总复杂度同样是 \(O(nlogn)\)

#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN = 50000+9;const int RANGE = 1000000;const int SIZE = 1500000;int n,m;int num[MAXN];struct T{    int ls,rs;    int sum;}tree[SIZE];int rt[MAXN];int head[RANGE+9];int pred[MAXN];int cnt;int insert(int pre,int left_range,int right_range,int pos){    int now=++cnt;    tree[now]=tree[pre];    tree[now].sum++;    if(left_range==right_range)        return now;    int mid=left_range+right_range>>1;    if(pos<=mid)tree[now].ls=insert(tree[pre].ls,left_range,mid,pos);    else tree[now].rs=insert(tree[pre].rs,mid+1,right_range,pos);    return now;}int query(int pre,int now,int left_range,int right_range,int pos){    if(left_range==right_range){        return tree[now].sum-tree[pre].sum;    }    int mid=left_range+right_range>>1;    if(pos<=mid)return query(tree[pre].ls,tree[now].ls,left_range,mid,pos);    else return tree[tree[now].ls].sum-tree[tree[pre].ls].sum+        query(tree[pre].rs,tree[now].rs,mid+1,right_range,pos);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&num[i]);        pred[i]=head[num[i]];        head[num[i]]=i;    }    for(int i=1;i<=n;i++)        rt[i]=insert(rt[i-1],0,RANGE,pred[i]);    scanf("%d",&m);    for(int i=1;i<=m;i++){        int l,r;        scanf("%d%d",&l,&r);        printf("%d\n",query(rt[l-1],rt[r],0,RANGE,l-1));    }    return 0;}