#6340. 「SDWC2018 Day2」矩形覆盖

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

题目描述

(a,b,c,d) 表示左下角在 (a,b) ,右上角在 (c,d) 的矩形。

支持三种操作:

I x1 y1 x2 y2:插入矩形 (x1,y1,x2,y2)

D x:删除第 x I 操作时插入的矩形(保证不会多次删除同一个矩形)。

Q x1 y1 x2 y2:求有多少矩形,与 (x1,y1,x2,y2) 至少有一个公共点。

1 \leq x1 \leq x2 \leq 10^9

1 \leq y1 \leq y2 \leq 10^9

试题来源: CodeChef QRECT

输入格式

输入数据的第一行包含一个整数 Q ,表示操作的总数。

接下来的 Q 行,每行包含一个操作。

输出格式

对于每个询问操作,输出一行表示对应的答案。

样例

样例输入 1

5
I 1 1 2 2
I 2 2 3 3
Q 3 3 4 4
D 2
Q 3 3 4 4

样例输出 1

1
0

样例输入 2

7
I 1 1 2 2
I 3 3 4 4
D 2
I 5 5 6 6
I 7 7 8 8
D 3
Q 7 7 8 8

样例输出 2

1

数据范围与提示

30\% 的数据, Q \leq 1000

30\% 的数据, Q \leq 100000 ,无删除操作。

40\% 的数据, Q \leq 100000