题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2743

思路：

设一个数组f[i],对于一个序列中的数,next(i)表示在原序列中位置i的数相同的在后面的数的位置。

那么，首先离散化序列来初始化next()，然后，对于每个在序列中首次出现的数，都令f[next[i]]=1（如果next(i)存在的话）。然后读入查询区间，按照左端点排序，从头到尾扫描一次，设现在位置在i，则对于每个区间[i,r]，答案即f[i]+...+f[r],处理完左端点i，若next(i)存在,f[next(i)]--,f[next(next(i))]++(若next(next(i))存在)，一直预处理出全部区间，然后输出答案即可。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

  

using namespace std;

  

#define MAXN 1000001

#define lowbit(x)(((~(x))+1)&x)

  

struct saver {

    int v,r;

    saver (){

        v=r=0;

    }

} a[MAXN];

  

int n,m,c;

int next[MAXN];

  

bool cmp(saver x,saver y){

    return (x.v<y.v||(x.v==y.v&&x.r<y.r));

}

  

int t[MAXN];

  

void add(int x,int y){

    while (x<=n){

        t[x]+=y;

        x+=lowbit(x);

    }

}

  

int sum(int x){

    int rec=0;

    while (x) {

        rec+=t[x];

        x-=lowbit(x);

    }

    return rec;

}

  

int ans[MAXN];

  

struct node {

    int r,T;

    node *next;

} *head[MAXN];

  

bool flag[MAXN];

  

int main(){

    scanf("%d%d%d",&n,&c,&m);

    for (int i=0;i++<n;){

        scanf("%d",&a[i].v);

        a[i].r=i;

    }

    sort(a+1,a+n+1,cmp);

    memset(next,0,sizeof(next));

    memset(flag,false,sizeof(flag));

    for (int i=0;i++<n-1;){

        if (a[i].v==a[i+1].v){

            next[a[i].r]=a[i+1].r;

        }

        if (a[i].v!=a[i-1].v){

            flag[a[i].r]=true;

        }

    }

    memset(t,0,sizeof(t));

    for (int i=0;i++<n;){

        if (flag[i]&&next[i]){

            add(next[i],1);

        }

    }

    memset(head,0,sizeof(head));

    for (int i=0;i++<m;){

        int l,r;

        scanf("%d%d",&l,&r);

        node *p=new(node);

        p->r=r;

        p->T=i;

        p->next=head[l];

        head[l]=p;

    }

    for (int i=0;i++<n;){

        for (node *p=head[i];p;p=p->next){

            ans[p->T]=sum(p->r);

        }

        if (next[i]){

            add(next[i],-1);

            if (next[next[i]]){

                add(next[next[i]],1);

            }

              

        }

    }

    for (int i=0;i++<m;){

        printf("%d\n",ans[i]);

    }

    return 0;

}