jiry_2's Blog

为了求矩形中的点的数量，首先可以想到的就是二维线段树或者二维树状数组，但是这道题的数据范围比较大，即使离散化之后还有200万多的点，会超空间。所以只能用一维的树状数组，可以先把所有点（包括查询矩形的四个顶点）按照第一关键字Y轴升序排序，第二关键字X轴升序排序。然后离散化，然后再扫一遍，如果是点就插入到树状数组中，如果是查询就求和，其值为右上角为改点，左下角为原点的矩形内的点，每个查询可以通过四个顶点的加减来考虑。有两点要考虑：1.要考虑边界，可以通过给点设值来排序。2.对N=0的情况要特判。

program p1935;
	const
		p:array[0..4] of longint=(4,1,3,5,2);
	type
		tree=record
			x,y:longint;
		end;
		num=record
			x,y,sx,pd,ls:longint;
		end;
		question=record
			x1,x2,y1,y2:longint;
			w:array[0..4] of longint;
		end;
		hzb=record	
			x,sx:longint;
		end;
	var
		t:array[1..500000] of tree;
		q:array[1..500000] of question;
		x:array[0..3000000] of num;
		h:array[0..3000000] of longint;
		c:array[1..3000000] of longint;
		len,n,m,i,j:longint;
	procedure add(k1,k2,k3,k4:longint);
		begin
			inc(len);
			x[len].x:=k1;
			x[len].y:=k2;
			x[len].sx:=k4;
			x[len].pd:=k3;
		end;
	function bo(k1,k2:longint):boolean;
		begin
			if x[k1].y<x[k2].y then exit(true);
			if x[k1].y>x[k2].y then exit(false);
			if x[k1].pd<=1 then exit(true);
			if x[k2].pd<=1 then exit(false);
			if x[k1].x<x[k2].x then exit(true);
			if x[k1].x>x[k2].x then exit(false);
			if x[k1].pd<=x[k2].pd then exit(true);
			exit(false);
		end;
	procedure quick(first,en:longint);
		var
			i,j:longint;
		begin
			{writeln(first,' ',en);}
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				{writeln(x[i].x,' ',x[i].y,' ',x[i].pd);
				writeln(x[j].x,' ',x[j].y,' ',x[j].pd);
				writeln(x[0].x,' ',x[0].y,' ',x[0].pd);}
				while (i<j) and (bo(0,j)=true) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (bo(i,0)=true) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then quick(first,i-1);
			if i<en-1 then quick(i+1,en);
		end;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; h[0]:=h[i];
			while i<j do begin
				while (i<j) and ((x[h[j]].x>x[h[0]].x) or ((x[h[j]].x=x[h[0]].x)) and (p[x[h[j]].pd]>=p[x[h[0]].pd])) do dec(j);
				if i<j then h[i]:=h[j];
				while (i<j) and ((x[h[i]].x<x[h[0]].x) or ((x[h[i]].x=x[h[0]].x)) and (p[x[h[i]].pd]<p[x[h[0]].pd])) do inc(i);
				if i<j then h[j]:=h[i];
			end;
			h[i]:=h[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	function lowbit(k:longint):longint;
		begin
			exit(k and -k);
		end;
	procedure add(k:longint);
		var
			i,j:longint;
		begin
			i:=k;
			while i<=len do begin
				inc(c[i]);
				i:=i+lowbit(i);
			end;
		end;
	function total(k:longint):longint;
		var
			i,j,num:longint;
		begin
			i:=k; num:=0;
			while i>0 do begin
				num:=num+c[i];
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	begin
		readln(n,m); len:=0;
		fillchar(x,sizeof(x),0);
		for i:=1 to n do begin
			readln(t[i].x,t[i].y);
			add(t[i].x,t[i].y,2,i);
		end;
		if n=0 then begin
			for i:=1 to m do
				writeln(0);
			exit;
		end;
		for i:=1 to m do begin
			readln(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
			add(q[i].x1,q[i].y1,1,i);
			add(q[i].x2,q[i].y2,3,i);
			add(q[i].x1,q[i].y2,4,i);
			add(q[i].x2,q[i].y1,0,i);
		end;
		quick(1,len);
		fillchar(c,sizeof(c),0);
		for i:=1 to len do
			h[i]:=i;
		sort(1,len);
		for i:=1 to len do
			x[h[i]].ls:=i;
		for i:=1 to len do
			if x[i].pd=2 then 
				add(x[i].ls)
			else 
				q[x[i].sx].w[x[i].pd]:=total(x[i].ls);
		for i:=1 to m do begin
			writeln(q[i].w[3]+q[i].w[1]-q[i].w[0]-q[i].w[4]);
		end;
	end.