区间查询
例题:
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