Description：

一个二维平面上有 $n$ 个直上直下的线段，每个人可以水平左右移动，不能穿过墙，问在即使有一个线段消失还能保证不会有两个人移动到横坐标相同的位置的情况下最多能有几个人。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

我们可以用一个四元组 $(l_2,l_1,r_1,r_2)$ 来表示一个放置坦克的方案，四个数分别表示左边第二面墙，左边第一面墙，右边第一面墙，右边第二面墙，那么两个四元组互相合法当且仅当他们之间有两条边，也就是说 $r_1\leqslant l_2$ 并且 $r_2\leqslant l_1$ ，那么设 $dp[i]$ 表示决策到第 $i$ 个四元组时的答案，有转移： $$ dp[i]=\max(dp[j]\Big|r_1[j]\leqslant l_2[i]\land r_2[j]\leqslant l_1[i]) $$ 也就是说无论 $r_1[j]$ 还是 $l_1[i]$ 塌了都不影响合法性，观察到这是一个二维偏序 $DP$ ，那么我们可以用排序 $+$ 树状数组来搞，但是有一点复杂，我们把所有四元组按 $l_1$ 排序，然后每次 $dp$ 过的四元组存在 $r_2$ 的那个 $vector$ 里，如果有一个 $l_1'\geqslant r_2$ ，那么就把这个状态插入到树状数组 $r_1$ 的位置，然后每次查询 $l_2$ 的前缀和。

那么唯一的问题就是怎么求出所有的四元组，我们可以拿一个扫描线从下往上扫，在线段的最下面把这个线段加到 $set$ 里，然后每次加入会产生不超过四个四元组，分别是这个线段作为 $l_2,l_1,r_1,r_2$ 时的情况，于是对于这 $4n$ 个四元组 $DP$ 即可。

Code：

没有代码。