把问题看作,即需要分别求出两项的值,令前一项为sumr,后一项为suml;
用指针,确保记录时所有的数均在[1,r]或[1,l-1]范围内,即可对值域查询;
于是将问题离线,第一步用左端点升序排序;
当指针j==q[i].l时,记录suml[q[i].id]=getsum(x),否则在值域中添加a[j];
再将问题右端点升序排序,当指针j==q[i].r+1时,记录sumr[q[i].id]=getsum(x),否则在值域中添加a[j];
最后统一输出sumr[i]-suml[i]即可;
Code:
#include<bits/stdc++.h> using namespace std; struct question { int l,r,x,id; }q[100005]; int c[100005],a[100005],suml[100005],sumr[100005],n,m,maxn; bool cmp1(question a,question b) { return a.l<b.l; } bool cmp2(question a,question b) { return a.r<b.r; } int lowbit(int x) { return x&(-x); } void add(int x,int d) { for(;x<=maxn;x+=lowbit(x))c[x]+=d; } int getsum(int x) { int ret=0; for(;x>=1;x-=lowbit(x))ret+=c[x]; return ret; } int main() { scanf("%d%d",&n,&m); int i,j; for(i=1;i<=n;i++)scanf("%d",&a[i]),maxn=max(maxn,a[i]); for(i=1;i<=m;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].id=i; } sort(q+1,q+m+1,cmp1);j=1; for(i=1;i<=m;i++) { while(j<q[i].l)add(a[j++],1); suml[q[i].id]=getsum(q[i].x); } sort(q+1,q+m+1,cmp2);j=1; memset(c,0,sizeof(c)); for(i=1;i<=m;i++) { while(j<=q[i].r)add(a[j++],1); sumr[q[i].id]=getsum(q[i].x); } for(i=1;i<=m;i++)printf("%d\n",sumr[i]-suml[i]); return 0; }