记录编号	512318	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.840 s
提交时间	2018-10-02 23:46:18	内存使用	16.71 MiB

#include<cstdio>
#include<vector>
using namespace std;
class Que
{
public:
    int num,val;
};
int n,m;
int num[50001];
int appear[1000001];//最新一次出现
int bit[50001];
vector<Que> query[1000001];//以r为右端点的问题
int ans[200001];
int lowbit(int x)
{
    return x&-x;
}
void add(int val,int pos)
{
    while(pos<=n)
    {
        bit[pos]+=val;
        pos+=lowbit(pos);
    }
    return;
}
int sum(int pos)
{
    int ret=0;
    while(pos>0)
    {
        ret+=bit[pos];
        pos-=lowbit(pos);
    }
    return ret;
}
int main()
{
    freopen("diff.in","r",stdin);
    freopen("diff.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        Que Q;
        Q.num=i;
        Q.val=l;
        query[r].push_back(Q);
    }
    for(int i=1;i<=n;i++)
    {
        add(1,i);//假设不同，bit[i]中存控制下的不同数
        if(appear[num[i]]==0)
        {//结果真不同
            appear[num[i]]=i;//记下最新位置
        }
        else
        {//假不同
            add(-1,appear[num[i]]);//从上一个同处-1
            appear[num[i]]=i;
        }
        for(int j=0;j<query[i].size();j++)
        {
            ans[query[i][j].num]=sum(i)-sum(query[i][j].val-1);//得到答案
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}