@[toc]

题目链接：[SDOI2009]HH的项链

时间限制： C/C++ 1秒，其他语言2秒
空间限制： C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一 段贝壳，思考它们所表达的含义。
HH不断地收集新的贝壳，因此他的项链变得越来越长。
有一天，他突然提出了一 个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答。。。因为项链实在是太长了。于是，他只 好求助睿智的你，来解决这个问题。
输入描述:
第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
N ≤ 50000，M ≤ 200000。
输出描述:
M行，每行一个整数，依次表示询问对应的答案。
示例1
输入

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

输出

2
2
4

题目大意

求区间不相同的数字有几个

解题思路

本菜鸡使用了离线的树状数组的做法，将要求需要查询的区间按照右边值按照从小到大的排列方式，进行查找，然后进行查找，我们可以既然按照有边界从小到大查询，我们可以用一个数组边标记这个值是否之前出来过，如果没出来那么就把这个值标记为当前的位置，如果出来过那么就从标记的位置开始向上减，最后再在这个位置以后向上加。这样我们就可以按照树状数组求区间和来解决了。
比如说123425，这个数组，第五个位置的2出现时标记数组pos[2]=2记录的是上个位置；所以add（2，-1）；然后add（5,1）；如果没有标记过就直接add（5，1），我们这样操作就不会影响求后面的了，当求区间（3,5）那么就是sum（5）-sum（3-1）；

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000100];//存输入数值
int f[1000100];//记录是否出现
int c[1000100];//树状数组维护前缀和
int pos[1000100];//标记每个值对应的位置
int ans[1000100];//记录答案用的
int n,m;
struct node{
    int l,r;
    int id;//标记这个区间是第几次输入进来的
    //这个是用于告诉sort如何排序
    //按照右边界从小到大排序
    bool operator < (const node &x) const{
            return r<x.r;
    }
}tre[1000100];
//树状数组的更新操作
void add(int x,int k){
    for(int i=x;i<=n;i+=(i&-i)) c[i]+=k;
}
int sum(int x){//树状数组的求和操作
    int an=0;
    for(int i=x;i;i-=(i&-i)) an+=c[i];
    return an;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>tre[i].l>>tre[i].r;tre[i].id=i;
    }
    sort(tre+1,tre+1+m);
    int k=1;
    for(int i=1;i<=m;i++)
    {
        for(k;k<=tre[i].r;k++)
        {
            if(f[a[k]])//如果这个值出现
            {
                add(f[a[k]],-1);//就从上次出现的位置开始减
            }
            add(k,1);//这个位置再重新加
            f[a[k]]=k;//记录这次出现的位置
        }
        ans[tre[i].id]=sum(tre[i].r)-sum(tre[i].l-1);//求答案
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}