#P18292. Just-in-Time Render Analysis
Just-in-Time Render Analysis
Just-in-Time Render Analysis
你正在开发浏览器,页面中的每个元素用平面上的一个轴对齐矩形表示。任意两个矩形要么一个严格包含另一个,要么完全分离;它们的边界不相交,甚至不会只接触一个点。
浏览器按层渲染:首先渲染不被其他矩形包含的元素,将它们移除;接着渲染剩余元素中最外层的元素,如此反复。最外层元素的渲染深度为 ,其他元素的渲染深度为所有严格包含它的元素的最大渲染深度加 。
每个元素有一个动画开关,初始均关闭。一个元素被称为有动画的元素,当且仅当它自身或它所包含的某个元素的动画开关开启。一个元素即使自己的开关关闭,也可能因为内部元素而有动画。
你需要在线处理开关切换,并回答:给定渲染深度 ,这一深度有多少个有动画的元素?
输入格式
第一行包含两个整数 (),分别表示元素数和事件数。
接下来 行,每行四个整数 ,表示一个矩形的左下角和右上角,满足
元素按输入顺序编号为 到 。矩形满足前述严格包含或完全分离的条件,且边界之间没有任何交点。
接下来 行,依次给出事件:
^ i:切换第 个元素的动画开关,开启变关闭、关闭变开启,其中 。? k:询问渲染深度为 的有动画元素数。保证 ,且 不超过所有元素的最大渲染深度。
初始所有开关均关闭,保证至少有一次询问。输入仅有一组数据。
输出格式
对每个 ? 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