5355: Restore Atlantis II
内存限制：512 MB
时间限制：7.000 S
评测方式：文本比较
命题人：
提交：4
解决：1
题目描述
There are n ancient Greek maps describing the fabled islands Atlantis. The maps are labeled by 1,2,…,n. The i-th map shows the rectangle area Ri is a part of Atlantis. The sides of all rectangles are parallel to the axes. There may be multiple islands, and the rectangles may overlap.
Unfortunately, some maps are even unreliable so they will not be considered. You will be given q queries. In the i-th query, you will be given two integers si and ti (1≤si≤ti≤n). Please write a program to figure out the total area of Atlantis when only maps labeled by k (si≤k≤ti) are reliable.
Unfortunately, some maps are even unreliable so they will not be considered. You will be given q queries. In the i-th query, you will be given two integers si and ti (1≤si≤ti≤n). Please write a program to figure out the total area of Atlantis when only maps labeled by k (si≤k≤ti) are reliable.
输入
The first line contains a single integer T (1≤T≤3), the number of test cases. For each test case:
The first line of the input contains two integers n and q (1≤n,q≤100000), denoting the number of maps and the number of queries.
In the next n lines, the i-th line contains four integers xai, yai, xbi and ybi (0≤xai<xbi≤109, 0≤yai<ybi≤109), describing the i-th map Ri. (xai,yai) is the southwest corner of Ri, and (xbi,ybi) is the northeast corner of Ri.
In the next q lines, the i-th line contains two integers si and ti (1≤si≤ti≤n), describing the i-th query.
It is guaranteed that all the values of xai, yai, xbi, ybi, si and ti are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
The first line of the input contains two integers n and q (1≤n,q≤100000), denoting the number of maps and the number of queries.
In the next n lines, the i-th line contains four integers xai, yai, xbi and ybi (0≤xai<xbi≤109, 0≤yai<ybi≤109), describing the i-th map Ri. (xai,yai) is the southwest corner of Ri, and (xbi,ybi) is the northeast corner of Ri.
In the next q lines, the i-th line contains two integers si and ti (1≤si≤ti≤n), describing the i-th query.
It is guaranteed that all the values of xai, yai, xbi, ybi, si and ti are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
输出
For each query, print a single line containing an integer, denoting the total area using the information of all reliable maps in this query.
样例输入 复制
1
3 6
10 10 20 20
12 12 22 22
15 15 25 25
1 1
2 2
3 3
1 2
2 3
1 3样例输出 复制
100
100
100
136
151
187