[SDOI2009] HH的项链（树状数组）

题目大意

Description

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

Input

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

Output

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

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

HINT

对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。

解题报告

看了黄学长的blog然后手推了一下就懂了……感谢h学长orz

贴一下黄学长精炼的解析：

#include<bits/stdc++.h>
using namespace std;
const int N = 1000500;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,mx;
int a[N],next[N],t[N],p[N];
struct data{
  int l,r,id,ans;
}q[N];
bool cmp1(data a,data b) {return a.l==b.l?a.r<b.r:a.l<b.l;}
bool cmp2(data a,data b) {return a.id < b.id;}
int lowbit(int x){return x&(-x);}

void modify(int x,int v)
{
    while(x<=n){
        t[x] += v;
        x += lowbit(x);
    }
}

int query(int x)
{
    int sum = 0;
    while(x>0){
        sum += t[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    n=read();
    for(int i = 1; i <= n;i++)
        a[i]=read(),mx=max(mx,a[i]); //输入每个位置的珍珠是哪种类型的，取出类型数 

    for(int i = n; i > 0; i--) //（**要背的**） 
        next[i] = p[a[i]],p[a[i]] = i; //p[i]记录下一种颜色所在的位置 

    for(int i = 1; i <= mx; i++)
        if(p[i]) modify(p[i],1);  //把每种颜色的第一个位置的计数+1 

    m = read();
    for(int i = 1;i <= m; i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;  //离线读入询问 

    sort(q + 1, q + m + 1, cmp1);  //所有询问按左端点排序 

    int l = 1;
    for(int i = 1; i <= m; i++){
        while(l < q[i].l){
            if(next[l])  modify(next[l],1);  //next不为0说明出现了不止一次
                     //那就在第二次出现的位置再加计数 
            l++;
        }
        q[i].ans = query(q[i].r) - query(q[i].l - 1);  //前缀和 
    }
    sort(q + 1, q + m + 1, cmp2); //把询问顺序还原 
    for(int i = 1; i <= m; i++)   printf("%d\n",q[i].ans); //按原序输出结果 
    return 0;
}