题目链接：https://www.luogu.org/problemnew/show/P1972
题目大意：


对于一个查询[L, R]，如果一个数组重复在数组中出现[1, R]，我们只关心它最后一次出现的位置。

查询[2, 4]和[1, 5]，我们按R排序。

p为首指针, 我们建立一棵权值数状数组。


现在可以得到[2, 4]的不同元素个数，query(4)-query(1)=3


现在可以得到[1, 5]的不同元素个数：query(5)-query(0)=3

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x-1)*Len+1)

struct node
{
    int L, R, k;
}q[500050];

int sum[1000010]={0};
int a[500050], n=1000010;//数组的最大值，太大时离散化
int vis[1000010]={0};
int ans[500050]={0};

int cmp(node a, node b)
{
    return a.R<b.R;
}

void add(int p, int y)
{
    while(p<=n)
    {
        sum[p]+=y;
        p+=(p&-p);
    }
}

int cx(int p)
{
    int ans=0;
    while(p)
    {
        ans+=sum[p];
        p-=(p&-p);
    }
    return ans;
}

int main()
{
    int n, m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].L,&q[i].R);
        q[i].k=i;
    }
    sort(q+1, q+1+m, cmp);//按查询的R排序
    
    int it=1;
    for(int i=1;i<=m;i++)
    {
        for(; it<=q[i].R;it++)
        {
            if(vis[a[it]])//这个数之前出现过
            {
                add(vis[a[it]], -1);//取消标记
            }
            vis[a[it]]=it;//记录最大位置
            
            add(it, 1);//添加新标记
        }

        it=q[i].R+1;
        ans[q[i].k]=cx(q[i].R)-cx(q[i].L-1);//查询
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }

    return 0;
}