离线二维数点

问题：给你一个长度为n的序列，m次询问，每次询问区间[l,r]中小于等于x的元素个数。

对于此种问题，最简单的解法就是扫描线+树状数组。这种问题满足离线性质，可以先把询问存下来，我们对原序列扫描，对于[l,r]的询问，设[1,l-1]中小于等于x的元素个数为a，[1,r]中的为b，则答案就是b-a(类似差分思想)。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;int n,m,a[N],ans[N],tr[N];
struct node{int x,id,tag;
};
vector<node> q[N];//q[i]相当于处理差分(上述所说的b-a)的数组，要弄清它的含义//树状数组基本操作
int lowbit(int x){return x&-x;
}
void add(int x,int v){for(int i=x;i<N;i+=lowbit(i)) tr[i]+=v;
}
int query(int x){int res=0;for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];return res;
}int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);//若值域很大的话，还需要离散化for(int i=1;i<=m;i++){int l,r,x;scanf("%d %d %d",&l,&r,&x);q[l-1].push_back(node{x,i,-1});//-aq[r].push_back(node{x,i,1});//b}for(int i=1;i<=n;i++){add(a[i],1);for(int j=0;j<q[i].size();j++){ans[q[i][j].id]+=q[i][j].tag*query(q[i][j].x);//一个询问遍历完后，得到的结果是b-a}}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}