求区间内数的种类个数（静态）

区间查询

例题：

P1972 [SDOI2009]HH的项链

原题链接

题目大意：求某一段贝壳中，包含了多少种不同的贝壳

首先整理出所有要求的区间的l，r

根据 r 从小到大排序

举栗子：

1、2、3、4、3、5

对于区间1~6的不同数的个数为5，对于数字3来说如果有多个3只有该区间内最后一个3有贡献值

相当于[1,2,3,4,5,6]的值为[1,1,0,1,1,1]

用树状数组维护

代码：

#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,m;
int a[1000006],f[4000006];
int pos[1000006];
struct node
{
    int x,y;
    int id,val;
}e[1000006];
bool cmp(node a,node b)
{
    if(a.y<b.y)
    {return 1;}
    return 0;
}
bool CMP(node a,node b)
{
    if(a.id<b.id)
    {return 1;}
    return 0;
}
int lowbit(int x)
{return x&(-x);}
void insertt(int x,int y)
{
    while(x<=n)
    {
        f[x]+=y;
        x+=lowbit(x);
    }
}
int query(int x,int y)
{
    x--;
    int ans1=0,ans2=0;
    while(x>0)
    {
        ans1+=f[x];
        x-=lowbit(x);
    }
    while(y>0)
    {
        ans2+=f[y];
        y-=lowbit(y);
    }
    return ans2-ans1;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {read(a[i]);}
    read(m);
    for(int i=1;i<=m;i++)
    {
        read(e[i].x);
        read(e[i].y);
        e[i].id=i;
    }
    sort(e+1,e+1+m,cmp);
    int ip=1;
    for(int i=1;i<=m;i++)
    {
        while(ip<=e[i].y)
        {
            int now=a[ip];
            if(pos[now]==0)
            {
                pos[now]=ip;
                insertt(ip,1);
            }
            else
            {
                insertt(pos[now],-1);
                pos[now]=ip;
                insertt(ip,1);
            }
            ip++;
        }
        e[i].val=query(e[i].x,e[i].y);
    }
    sort(e+1,e+1+m,CMP);
    for(int i=1;i<=m;i++)
    {printf("%d\n",e[i].val);}
    return 0;
} 

123