题目描述

给定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 个整数 l 1, 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

题目来源

By wangyisong1996