#P14946. [uoi2018]Olya and Plane奥莉娅与平面

[uoi2018]Olya and Plane奥莉娅与平面

题目描述

小女孩奥莉娅是完美人类的典范:她每天都解题。然而,在家学习几乎不可能,因为她家里住着一只调皮的猫康斯坦丁,它总会找机会搞破坏。

生日时,奥莉娅收到了一大块白色笛卡尔平面作为草稿纸。康斯坦丁立刻想把这个漂亮的礼物弄坏。

这块平面是一个白色正方形,左下角坐标为 (0,0)(0,0),右上角坐标为 (N,N)(N,N)。为了方便,奥莉娅在平面的四个角,即 (0,0)(0,0)、(N,0)(N,0)、(0,N)(0,N)、(N,N)(N,N),各放了一瓶墨水,然后坐下来写一场复杂的比赛。

当奥莉娅正在写题时,康斯坦丁可能走过去“偶然”打翻任意一瓶墨水。此时,以该墨水瓶所在角和点 (x,y)(x,y) 为对角的矩形区域会被彻底弄脏,并全部染成黑色。奥莉娅当然会喊几声,但也只能重新装满墨水瓶继续写比赛。之后康斯坦丁还可以再次打翻墨水,染黑另一个区域。

有时,奥莉娅遇到特别困难的题目,会决定在平面的某个区域记录想法。她总是选择一个边与坐标轴平行的矩形区域。显然,她需要知道所选区域中有多少面积已经被墨水覆盖。奥莉娅忙于解题,所以需要你来帮助她。

任务

请根据比赛期间发生的事件,帮助奥莉娅求出查询矩形中被猫弄脏的面积。

输入格式

第一行包含两个整数 N,QN,Q(1≤N,Q≤1051 \le N,Q \le 10^5),分别表示平面的边长和事件数量。

接下来 QQ 行描述事件。每行首先包含一个整数 tt。

若 1≤t≤41 \le t \le 4,表示康斯坦丁打翻了对应角落的墨水瓶。此时接下来给出两个整数 x,yx,y(0≤x,y≤N0 \le x,y \le N),表示被染黑矩形区域的另一个对角点。

四个墨水瓶的位置如下:

  1. 左下角;
  2. 右下角;
  3. 左上角;
  4. 右上角。

若 t=0t=0,接下来给出四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2(0≤x1<x2≤N0 \le x_1<x_2\le N,0≤y1<y2≤N0 \le y_1<y_2\le N),表示奥莉娅选择的查询矩形,其对角点为 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2)。

保证输入中至少有一个 t=0t=0 的事件,且猫染黑的矩形面积非零。

输出格式

对于每个类型 00 的查询,按输入顺序输出一行一个整数,表示对应矩形中被猫弄脏的面积。

输入

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

输出

10

子任务

1.(5 分)1≤N,Q≤1001 \le N,Q \le 100;

2.(6 分)1≤N,Q≤10001 \le N,Q \le 1000,t∈{0,1,2}t \in \{0,1,2\};

3.(8 分)1≤N,Q≤10001 \le N,Q \le 1000;

4.(14 分)1≤N,Q≤500001 \le N,Q \le 50000,类型 00 的查询数 量不超过 2020;

5.(12 分)1≤N,Q≤500001 \le N,Q \le 50000,t∈{0,1}t \in \{0,1\}, 且对所有类型 11 的染色事件,若事件 aa 晚于事件 bb, 则 xa≤xbx_a \le x_b 且 ya≥yby_a \ge y_b;

6.(8 分)1≤N,Q≤500001 \le N,Q \le 50000,t∈{0,1}t \in \{0,1\};

7.(10 分)1≤N,Q≤500001 \le N,Q \le 50000,t∈{0,1,2}t \in \{0,1,2\};

8.(13 分)1≤N,Q≤500001 \le N,Q \le 50000;

9.(9 分)t∈{0,1}t \in \{0,1\};

10.(8 分)t∈{0,1,2}t \in \{0,1,2\}; 11.(7 分)无额外限制。