#P6396. 万宁俄罗斯方块(大招版)

    ID: 6433 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-懒标记线段树二分查找区间合并欧拉示性数

万宁俄罗斯方块(大招版)

题目描述

地面是无限长的水平直线。依次将 nn 个矩形沿竖直方向从上方落下。第 ii 个矩形的左右边界分别固定在 x=lix=l_i 和 x=rix=r_i,高度为 hih_i。矩形落到不能再下移时固定。矩形内部不能重叠,边界接触是允许的。

在地面上方,未被矩形覆盖的区域按四连通划分。被地面或矩形封闭、面积大于零的连通区域称为一个洞。求每个矩形落下并固定后新形成的洞数。

输入格式

第一行一个整数 nn。接下来 nn 行,每行三个整数 li,ri,hil_i,r_i,h_i,依次给出矩形的左右边界和高度。

输出格式

输出 nn 行。第 ii 行给出第 ii 个矩形落下并固定后新形成的洞数。

样例

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

第 3 个矩形落下后形成 1 个洞,第 7 个矩形落下后形成 2 个洞。原 PDF 的第 2 页给出了堆叠示意图。

数据范围

对全部数据,1≤n≤1061\le n\le10^6,0≤li<ri≤1050\le l_i<r_i\le10^5,1≤hi≤1031\le h_i\le10^3。

子任务 nn 的上界 分数
1 11 3
2 10210^2 17
3 10310^3 30
4 10510^5
5 10610^6 20

题目为「HNOI 2009」积木游戏的加强版。原题面及样例图 PDF