传送门
题目大意
给出一个长度为 n n n的序列,进行 m m m次询问。
每次询问区间 [ l , r ] [l,r] [l,r]内,有多少个数字 x x x刚好出现了 x x x次。
思路
枚举右端点 r r r,维护左端点 l l l,设法将 s u m ( l , r ) s u m ( l , r ) sum(l,r) 表示为区间内的合法数字个数
所以以区间 [ 2 , 2 , 2 , 2 ] [ 2 , 2 , 2 , 2 ] [2,2,2,2]为例:
- r = 1 r = 1 r=1,左端点的贡献分别为: [ 0 , 0 , 0 , 0 ] [ 0 , 0 , 0 , 0 ] [0,0,0,0];
- r = 2 r = 2 r=2,左端点的贡献分别为: [ 1 , 0 , 0 , 0 ] [ 1 , 0 , 0 , 0 ] [1,0,0,0];
- r = 3 r = 3 r=3,左端点的贡献分别为: [ − 1 , 1 , 0 , 0 ] [ − 1 , 1 , 0 , 0 ] [−1,1,0,0];
- r = 4 r = 4 r=4,左端点的贡献分别为: [ 0 , − 1 , 1 , 0 ] [ 0 , − 1 , 1 , 0 ] [0,−1,1,0];
所以可以看出规律,只需要维护上述规律即可将贡献维护成前缀和。
代码
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
int a[maxn],n,m,ans[maxn],tr[maxn];
vector<PII>q[maxn];
vector<int>g[maxn];
int lowbit(int x){
return x&-x;
}
void update(int pos,int val){
while(pos<=n){
tr[pos]+=val;pos+=lowbit(pos);
}
}
int query(int pos){
int res=0;
while(pos){
res+=tr[pos];pos-=lowbit(pos);
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
q[r].push_back({l,i});
}
for(int i=1;i<=n;i++){
int x=a[i];
if(x<=n){
g[x].push_back(i);
int siz=g[x].size();
if(siz>=x){
update(g[x][siz-x],1);
if(siz-x-1>=0) update(g[x][siz-x-1],-2);
if(siz-x-2>=0) update(g[x][siz-x-2],1);
}
}
for(int j=0;j<q[i].size();j++){
PII t=q[i][j];
int l=t.first,id=t.second;
ans[id]=query(i)-query(l-1);
}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}