乱搞做法求正确性
查看原帖
乱搞做法求正确性
547787
__Refine__楼主2025/1/4 15:56

把每个点和矩形的端点(x1,y1,xx,yyx-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;
 }
2025/1/4 15:56
加载中...