把每个点和矩形的端点(x−1,y−1,xx,yy)记录在一个数组里,排序然后用树状数组维护求出每个点的二维前缀和。介于本人一向细节出错严重,请各位大佬帮忙看看做法是否正确。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
struct tree
{
int kk,tre[MAXN];
void modify(int x,int y)
{
for(;x<=kk;x+=x&-x) tre[x]+=y;
}
int query(int x)
{
int all=0;
for(;x;x-=x&-x) all+=tre[x];
return all;
}
}tt;
struct dian
{
int x,y,num,sum;
}d[MAXN<<2];
struct ask
{
int x,y,xx,yy;
}qu[MAXN];
int n,m,a[MAXN*3],tot,cnt;
map<int,map<int,int> > ma;
bool cmp1(dian x,dian y)
{
if(x.x==y.x)return x.y<y.y;
return x.x<y.x;
}
void solve()
{
for(int i=1;i<=cnt;i++)
{
tt.modify(d[i].y,d[i].num);
d[i].sum=tt.query(d[i].y);
if(d[i].num==0){
//cout<<d[i].sum<<" "<<d[i].x<<" "<<d[i].y<<endl;;
ma[d[i].x][d[i].y]=d[i].sum;
//cout<<ma[3][3];
}
}
}
int main()
{
cin>>n>>m;
tt.kk=MAXN;
for(int i=1;i<=n;i++)
{
cnt++;
scanf("%d%d",&d[cnt].x,&d[cnt].y);
a[++tot]=d[cnt].x,a[++tot]=d[cnt].y;
d[cnt].num=1;
}
for(int i=1;i<=m;i++)
{
int x,y,xx,yy;
scanf("%d%d%d%d",&x,&y,&xx,&yy);
d[++cnt]=(dian){x-1,y-1,0,0};
d[++cnt]=(dian){x-1,yy,0,0};
d[++cnt]=(dian){xx,y-1,0,0};
d[++cnt]=(dian){xx,yy,0,0};
qu[i]=(ask){x-1,y-1,xx,yy};
a[++tot]=x-1,a[++tot]=xx,a[++tot]=y-1,a[++tot]=yy;
}
sort(a+1,a+1+tot);
int st=unique(a+1,a+1+tot)-(a+1);
for(int i=1;i<=cnt;i++)
{
d[i].x=lower_bound(a+1,a+1+st,d[i].x)-a;
d[i].y=lower_bound(a+1,a+1+st,d[i].y)-a;
}
for(int i=1;i<=m;i++){
qu[i].x=lower_bound(a+1,a+1+st,qu[i].x)-a;
qu[i].xx=lower_bound(a+1,a+1+st,qu[i].xx)-a;
qu[i].y=lower_bound(a+1,a+1+st,qu[i].y)-a;
qu[i].yy=lower_bound(a+1,a+1+st,qu[i].yy)-a;
}
sort(d+1,d+1+cnt,cmp1);
solve();
for(int i=1;i<=m;i++)
{
int ans=ma[qu[i].xx][qu[i].yy]+ma[qu[i].x][qu[i].y]-ma[qu[i].x][qu[i].yy]-ma[qu[i].xx][qu[i].y];
//cout<<ma[qu[i].xx][qu[i].yy];
printf("%d\n",ans);
}
return 0;
}