BZOJ 1935 SHOI2007 園丁的煩惱 樹狀數組

BZOJ 1935 SHOI2007 園丁的煩惱 樹狀數組

題目大意：給定平面上的一些點，多次詢問某個矩形中有多少個點

將每個詢問拆成4個 然後把所有詢問和點都按照橫坐標排序

對於每個詢問，將所有x值小於等於這個詢問的x的點的y值加入樹狀數組 然後在樹狀數組上查詢小於等於這個詢問的y值的點的數量

別被1000W嚇到了 如果不爆內存的話1E也是能搞的 套個log就沒多少了

#include 
#include 
#include 
#include 
#define M 500500
using namespace std;
struct point{
	int x,y;
	void Read()
	{
		scanf("%d%d",&x,&y);
		++x;++y;
	}
	bool operator < (const point &Y) const
	{
		return x < Y.x ;
	}
}points[M];
struct query{
	int x,y,pos,flag;
	query(){}
	query(int _,int __,int ___,int ____):
		x(_),y(__),pos(___),flag(____){}
	bool operator < (const query &Y) const
	{
		return x < Y.x ;
	}
}queries[M<<2];
int n,m,ans[M];
int c[10001000];
void Update(int x)
{
	for(;x<=10000000;x+=x&-x)
		c[x]++;
}
int Get_Ans(int x)
{
	int re=0;
	for(;x;x-=x&-x)
		re+=c[x];
	return re;
}
int main()
{
	int i,j,x1,y1,x2,y2;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		points[i].Read();
	sort(points+1,points+n+1);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		++x2;++y2;
		queries[i*4-3]=query(x1,y1,i,1);
		queries[i*4-2]=query(x1,y2,i,-1);
		queries[i*4-1]=query(x2,y1,i,-1);
		queries[i<<2 ]=query(x2,y2,i,1);
	}
	sort(queries+1,queries+m*4+1);
	for(i=1,j=1;i<=m<<2;i++)
	{
		for(;j<=n && points[j].x<=queries[i].x;j++)
			Update(points[j].y);
		ans[queries[i].pos]+=Get_Ans(queries[i].y)*queries[i].flag;
	}
	for(i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}