普通二维数点问题
- 对原点和查询点按x排序
- 权值树状数组计数
cpp
int a[N],c[N];
void add(int x,int y){
for(int i=x;i<N;i+=i&-i)c[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i;i&=i-1)ans+=c[i];
return ans;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int> ans(m+1);
vector<array<int,3>> q[n+1];
for(int i=1;i<=m;i++){
int l,r,x;
cin>>l>>r>>x;
q[l-1].push_back({i,x,-1});
q[r].push_back({i,x,1});
}
for(int i=1;i<=n;i++){
add(a[i],1);
for(auto &[id,x,op]:q[i])ans[id]+=op*query(x);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}