记录编号	290215	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	7.292 s
提交时间	2016-08-05 21:41:33	内存使用	72.79 MiB

/*
 *Problem : cogs1619
 *Name : ZXCVBNM_1
 *Time : 2016.8.5 21:08
 *Sta : AC
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
using namespace std;
#define MAXN 1000010
struct node
{
    int l,r,id;
}q[MAXN];
struct NODE
{
    int left,right,sum;
}tree[MAXN*4];
int a[MAXN],last[MAXN],now[MAXN],ans[MAXN];
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
void Pushup(int k){tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;}
void Build(int k,int l,int r)
{
    tree[k].left=l;tree[k].right=r;tree[k].sum=0;
    if(l==r)return;
    int mid=(l+r)/2;
    Build(k*2,l,mid);
    Build(k*2+1,mid+1,r);
}
void Update(int k,int lr,int U)
{
    if(tree[k].left==tree[k].right){tree[k].sum+=U;return;}
    int mid=(tree[k].left+tree[k].right)/2;
    if(lr<=mid)Update(k*2,lr,U);
    else Update(k*2+1,lr,U);
    Pushup(k);
}
int Query(int k,int ql,int qr)
{
    if(ql<=tree[k].left&&tree[k].right<=qr)return tree[k].sum;
    int mid=(tree[k].left+tree[k].right)/2;
    if(qr<=mid)return Query(k*2,ql,qr);
    else if(ql>mid)return Query(k*2+1,ql,qr);
    else return Query(k*2,ql,mid)+Query(k*2+1,mid+1,qr);
    Pushup(k);
}
bool cmp(node aa,node bb){return aa.r<bb.r;}
int main()
{
    //freopen("in","r",stdin);
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    int n,c,m,i,R;
    n=read();c=read();m=read();
    for(i=1;i<=n;i++)a[i]=read();
    for(i=1;i<=n;i++)
    {
        last[i]=now[a[i]];
        now[a[i]]=i;
    }
    for(i=1;i<=m;i++){q[i].l=read();q[i].r=read();q[i].id=i;}
    sort(q+1,q+m+1,cmp);
    R=0;
    Build(1,1,n);
    for(i=1;i<=m;i++)
    {
        while(R<q[i].r)
        {
            R++;
            if(last[last[R]]!=0)Update(1,last[last[R]],-1);
            if(last[R]!=0)Update(1,last[R],1);
        }
        ans[q[i].id]=Query(1,q[i].l,q[i].r);
    }
    for(i=1;i<=m;i++)printf("%d ",ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}