Description

公园里长满了树木，为了更加美观也能更方便公园里的行人，需要砍掉一些树木，增加一些散步小路。公园可看作一个平面直角坐标系，其中所有树木都生长在图中的整点上，并且没有两棵树在同一个位置。要建造的散步小路都是长方形的回路，且长方形的四边都与x轴或y轴平行，在建造这条小路时，需要把小路长方形四边上所有树木都砍掉。当然不同的小路之间可能有交点，甚至会有重叠，但在重叠部分上树木只在建第一次小路时砍掉。现在给出所有树木的坐标，再按建造顺序给出小路的坐标，求出在建造每条小路时分别需要砍掉多少棵树。

Input

数据的第一行为两个非负整数N和M,分别表示原有树木的数量和要建造小路的数量。

下面接着的N行，每行有两个整数，分别表示每棵树木的x坐标和y坐标。

下面接着的M行，每行有四个整数，x1,y1,x2,y2(x1<x2,y1<y2)，表示小路形成的长方形的四个顶点分别是(x1,y1),(x1,y2),(x2,y2),(x2,y1)。

Output

输出M行，每行一个整数，分别表示在建造每条小路时砍掉的树木的数量。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7 6
5 4
6 6
3 3 
7 6
7 4
5 2
6 2
2 3 4 5
2 6 7 7
1 3 2 6
6 4 7 5
1 1 3 3
1 0 6 2

Sample Output

1
2
3
4
5
6
1
2
0
1
0
2

Data Constraint

  • 对于30%的数据，N<=50,M<=50,所有坐标范围[-100，100]
  • 对于50%的数据，N<=1000,M<=1000,所有坐标范围[-10^9^,10^9^]
  • 对于100%的数据,N<=100000,M<=100000,所有坐标范围[-10^9^,10^9^]

Solution

首先，我们可以发现一些十分重点的字词。显然这些条件十分有用。

我们考虑这样一件事情，也就是说，我们把每一棵树分别按照以xx为第一关键字，yy为第二关键字和yy为第一关键字，xx为第二关键字排序，然后一一对应。

这样我们删除长方形的长和宽上的树的时候会发现它们是连续的一段，删除就会特别好删。

观察到，每一棵树只有在第一次修建会产生贡献，意思就是说，每一棵树最多被删一遍，又因为n≤105n \le 10^5，因此删除的总时间复杂度最多是O(nlog⁡n)O(n \log n)的。

于是乎我们可以考虑使用setset来对这些树进行维护，暴力删除，打的优美一点就能大幅度减小常数

注意这里可以不使用离散化，因为我们并没有使用线段树之类的算法。

直接的话大概是800800多msms，“常数性优化”后400400多

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <set>
#include <cstdio>
#define N 100005
#define sit set<Data>::iterator
using namespace std;
struct Data {
	int x,y,id;
	bool operator<(const Data a) const {
		if (x<a.x) return 1;
		if (x>a.x) return 0;
		return (y<a.y) ;
	}
};
sit px[N],py[N];
set<Data> a,b;
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=n;++i)
	{
		scanf("%d%d",&x,&y);
		Data c=Data{x,y,i};
		Data d=Data{y,x,i};
		a.insert(c),px[i]=a.find(c);
		b.insert(d),py[i]=b.find(d);
	}
	for (int ux,uy,vx,vy,ans;m--;)
	{
		scanf("%d%d%d%d",&ux,&uy,&vx,&vy);ans=0;
		if (!a.empty()) {
			sit i=a.lower_bound(Data{ux,uy,0}),c;
			while (i!=a.end() && (*i).x==ux && (*i).y<=vy)
			c=i++,++ans,b.erase(py[(*c).id]),a.erase(c);
		}
		if (!a.empty()) {
			sit j=a.lower_bound(Data{vx,uy,0}),c;
			while (j!=a.end() && (*j).x==vx && (*j).y<=vy)
			c=j++,++ans,b.erase(py[(*c).id]),a.erase(c);
		}
		if (!b.empty()) {
			sit i=b.lower_bound(Data{uy,ux,0}),c;
			while (i!=b.end() && (*i).x==uy && (*i).y<=vx)
			c=i++,++ans,a.erase(px[(*c).id]),b.erase(c);
		}
		if (!b.empty()) {
			sit j=b.lower_bound(Data{vy,ux,0}),c;
			while (j!=b.end() && (*j).x==vy && (*j).y<=vx)
			c=j++,++ans,a.erase(px[(*c).id]),b.erase(c);
		}
		printf("%d\n",ans);
	}
}