30 Pts 求调qaq
查看原帖
30 Pts 求调qaq
968688
TCY1234567楼主2024/12/26 10:18
#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x,y;
	
}e[2000005];
struct node2
{
	int x,y,id,flag;
}e2[2000005];
int ans[2000005];
int c[10000005];
bool cmp(node a,node b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmpp(node2 a,node2 b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
int sum(int x)
{
	int sum = 0;
	while(x)
	{
		sum+=c[x];
		x-=x&(-x);
	}
	return sum;
}
void update(int x)
{
	if(x==0) x++;
	for(;x<10000001;x+=x&-x)
	{
		c[x]++; 
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&e[i].x,&e[i].y);
	}
	
	int cnt = 0;
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		cnt++;e2[cnt].x = c;e2[cnt].y = d;e2[cnt].id = i;e2[cnt].flag = 1;
		cnt++;
		if(b)
		{
			e2[cnt].x = c;e2[cnt].y = b-1;e2[cnt].id = i;e2[cnt].flag = 0;
		}
		cnt++;
		if(a)
		{
			e2[cnt].x = a-1;e2[cnt].y = d;e2[cnt].id = i;e2[cnt].flag = 0;
		}
		cnt++;
		if(a&&b)
		{
			e2[cnt].x = a-1;e2[cnt].y = b-1;e2[cnt].id = i;e2[cnt].flag = 1;
		}
	}
	sort(e+1,e+n+1,cmp);
	sort(e2+1,e2+cnt+1,cmpp);
	int cntt = 1;
	for(int i=1;i<=cnt;i++)
	{
		while(e[cntt].x<=e2[i].x&&cntt<=n)
		{
			update(e[cntt].y);
			cntt++;
		}
		if(e2[i].flag==1) ans[e2[i].id]+=sum(e2[i].y);
		else ans[e2[i].id]-=sum(e2[i].y);
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
 }
2024/12/26 10:18
加载中...