A89672.「2017 山东二轮集训 Day7」领主

省选/NOI-

通过率:0%

时间限制:1.50s

内存限制:512MB

题目描述

在某个鬼畜的大陆上,有若干领主,这片大陆可以看做是一个无限平面,领主们会不断试图占领土地,具体来说,有三种行为:

  • I x1 y1 x2 y2 有一个新的领主想要试图占领以 $ (x_1, y_1) $ 为左上角,$ (x_2, y_2) $ 为右下角的矩形土地;
  • D x 第 $ x $ 个领主放弃了他的土地占领计划;
  • Q x1 y1 x2 y2 有秘密组织想知道,他们如果用 $ (x_1, y_1) $ 为左上角,$ (x_2, y_2) $ 为右下角的矩形土地开展活动,最多会与多少个领主发生冲突(若与某个领主想要占领的土地有重合点,即视为可能发生冲突)。

现在你知道所有的行为信息,需要回答秘密组织的问题。

输入格式

第一行一个正整数 $ n $ 表示操作总量。
接下来 $ n $ 行,每行形如上面三种操作中的一种。

输出格式

对于每个 Q 操作,输出一行表示答案。

输入输出样例

  • 输入#1

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

    输出#1

    1
    1

说明/提示

$ 1 \leq n \leq 100000 $

首页