题解

思路

沿用普通 LIS 的最小末尾值数组 $dp$：若把值域位置 $x$ 标为 $1$ 当且仅当某个 $dp_j=x$，则加入一个连续段 $[l,r]$ 的效果可以整体描述。

做法

先从位置 $l$ 起向右删除最靠左的至多 $r-l+1$ 个标记，再把区间 $[l,r]$ 的所有位置标为 $1$。这是逐个插入 $l,l+1,\ldots,r$ 并做 lower_bound 更新的等价批量操作。

把所有 $l_i$ 与 $r_i+1$ 离散化，相邻坐标之间的值域在所有操作中始终整体处理。线段树维护每段长度、当前标记数以及区间赋零或赋一的懒标记。删除时从 $l_i$ 对应位置向右递归：若整棵子树的标记数不超过剩余删除量就整段赋零，否则只进入包含第一个未删除标记的边界子树；随后将 $[l_i,r_i+1)$ 赋一。

复杂度

每次操作只经过对数个边界节点，总复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$，根节点的标记总数即为答案。