hack

hack @tzc_wk 的题解。

in:

3 1
1 2 6 3
2 4 5 5
3 1 4 6

ans:

10

out:

7

原因是 tzc 老师在处理联通块的时候用 set 直接进行区间删除是不对的，因为这些被删除的竖边还可能与接下来的矩形有交然后进行合并。

正确的做法是用 ODT 或线段树来维护颜色段均摊，一共只有 $O(n)$ 个段所以复杂度是 $O(n\log n)$ 的。