logo AlgoBeat OnlineJudge
登录 注册

#103567. [BZOJ 3567] AABB

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定N个与坐标轴平行的矩形(左下角和右上角坐标用四个整数x1,y1,x2,y2表示)。定义两个矩形相交,当存在一个点同时在这两个矩形内部(不包括边界)时。注意一个矩形跟它自身也是相交的。

现在有Q组询问,每组询问给定4个整数l1, r1,l2,r2,询问有多少对(i, j),满足l1 <=i <=r1,l2<= j<=r2,且矩形i与矩形j相交。

输入格式

第1行一个整数N。

接下来N行,每行4个整数x1,y1,x2,y2,第(i+1)行的整数表示第i个矩形的左下角和右上角坐标。接下来1行一个整数Q。

接下来Q行,每行4个整数l1,r1,l2,r2,表示一个询问。为了体现询问的在线性,输入的l1, r1, l2, r2都已经加密,你需要将这些数异或lastans得到真实的输入,其中lastans为上次询问的答案,一开始为0。

输出格式

Q行,每行一个整数,第i行表示第i个询问的答案。

样例

样例输入

5
1 1 3 3
2 2 4 4
3 1 4 2
1 2 4 3
1 3 2 5
5
1 5 1 5
10 10 8 8
1 3 1 5
5 3 6 4
6 0 6 0 

样例输出

11
0
7
5
3

数据范围与提示

1<=x1<x2<=N,1<=y1<y2<=N,1<=l1<=r1<=N,1<=l2<=r2<=

N。

N<=30000,Q<=30000。

由于是OJ上的题目,只有1组最大数据和若干组较小的数据。

解密后的样例输入如下:

5

1 1 3 3

2 2 4 4

3 1 4 2

1 2 4 3

1 3 2 5

5

1 5 1 5

1 1 3 3

1 3 1 5

2 4 1 3

3 5 3 5