矩阵内点数显然可以预处理前缀和然后简单容斥一下
具体就是设 $sum[i][j]$ 表示以 $(i,j)$ 为右上角，以 $(0,0)$ 为左下角的矩阵的点数
那么对于询问以 $(xa,ya)$ 为左下角，以 $(xb,yb)$ 为右上角的矩形点数
注意到询问区间是闭的，显然答案就是 $sum[xb][yb]-sum[xb][ya-1]-sum[xa-1][yb]+sum[xa-1][ya-1]$
但是此题坐标系太大
所以要离散化，扫描线，树状数组来维护一个矩阵内的点数
把所有点和询问离散化（一个询问变成 $4$ 个点 $(xa-1,ya-1),(xa-1,yb),(xb,ya-1),(xb,yb)$），按 $x,y$ 为一二关键字排序，$x,y$ 相同时实点先，询问点后
然后树状数组维护当前 $y$ 坐标小于等于某个数的点数，然后就可以用树状数组求 $sum$ 了
扫描的时候更新答案就好了
代码好写，注意树状数组维护时坐标要为正，所以集体+1
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7,M=1e7+7; int n,m,mx,cnt; struct dat{ int x,y,id,p;//位置x,y,询问编号id,对询问的贡献系数 inline bool operator < (const dat &tmp) const { if(x!=tmp.x) return x<tmp.x; return y!=tmp.y ? y<tmp.y : id<tmp.id;//注意x,y相同时,实点优先 } }d[M];//注意离散的点数比较大 int t[M],ans[N]; inline void add(int x) { while(x<M) t[x]++,x+=x&-x; } inline int ask(int x) { int res=0; while(x) res+=t[x],x-=x&-x; return res; } int main() { int a1,b1,a2,b2; cnt=n=read(),m=read(); for(int i=1;i<=n;i++) d[i].x=read()+1,d[i].y=read()+1; for(int i=1;i<=m;i++) { a1=read(),b1=read(),a2=read()+1,b2=read()+1; d[++cnt]=(dat){a1,b1,i,1}; d[++cnt]=(dat){a1,b2,i,-1}; d[++cnt]=(dat){a2,b1,i,-1}; d[++cnt]=(dat){a2,b2,i,1}; } sort(d+1,d+cnt+1); for(int i=1;i<=cnt;i++) { if(!d[i].id) { add(d[i].y); continue; } ans[d[i].id]+=d[i].p*ask(d[i].y); } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }