#P18292. Just-in-Time Render Analysis

Just-in-Time Render Analysis

Just-in-Time Render Analysis

你正在开发浏览器,页面中的每个元素用平面上的一个轴对齐矩形表示。任意两个矩形要么一个严格包含另一个,要么完全分离;它们的边界不相交,甚至不会只接触一个点。

浏览器按层渲染:首先渲染不被其他矩形包含的元素,将它们移除;接着渲染剩余元素中最外层的元素,如此反复。最外层元素的渲染深度为 00,其他元素的渲染深度为所有严格包含它的元素的最大渲染深度加 11。

每个元素有一个动画开关,初始均关闭。一个元素被称为有动画的元素,当且仅当它自身或它所包含的某个元素的动画开关开启。一个元素即使自己的开关关闭,也可能因为内部元素而有动画。

你需要在线处理开关切换,并回答:给定渲染深度 kk,这一深度有多少个有动画的元素?

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤5×1051\le n,q\le5\times10^5),分别表示元素数和事件数。

接下来 nn 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一个矩形的左下角和右上角,满足

1≤x1<x2≤109,1≤y1<y2≤109.1\le x_1<x_2\le10^9,\qquad 1\le y_1<y_2\le10^9.

元素按输入顺序编号为 11 到 nn。矩形满足前述严格包含或完全分离的条件,且边界之间没有任何交点。

接下来 qq 行,依次给出事件:

  • ^ i:切换第 ii 个元素的动画开关,开启变关闭、关闭变开启,其中 1≤i≤n1\le i\le n。
  • ? k:询问渲染深度为 kk 的有动画元素数。保证 0≤k0\le k,且 kk 不超过所有元素的最大渲染深度。

初始所有开关均关闭,保证至少有一次询问。输入仅有一组数据。

输出格式

对每个 ? k 事件,输出一行整数,表示这一深度有多少个有动画的元素。

样例

8 7
1 1 15 11
2 2 7 4
2 5 7 10
3 6 4 9
5 6 6 7
8 2 14 10
9 5 13 9
11 6 12 7
^ 4
^ 5
^ 8
? 0
? 1
? 2
? 3
1
2
3
1