我校 noi 模拟赛 T3。

设点 $A(x,y)$，可以发现：

• 如果点 $A$ 在 $W$ 型等腰三角形（顶点是 $(x',y')$）中，需要满足 $x+y \leq x'+y'$ 且 $x-y \geq x'-y'$；
• 如果点 $A$ 在 $N$ 型等腰三角形（顶点是 $(x',y')$）中，需要满足 $2x+y \leq 2x'+y'$ 且 $2x-y \geq 2x'-y'$。

这样可以做到 $O(n^2)$ 的暴力。

接下来，我们不妨先判断是否能够插入。（输出 FAIL）不难发现这一步与三角形的形状无关。

如果当前插入等腰三角形顶点是 $(x,y)$，我们需要判断在之前的操作中，是否有一个三角形包含 $(x,y)$。

考虑操作序列中未弹出的 $W$ 型三角形（顶点是 $(x',y')$），根据以上的结论，我们需要判断满足 $x+y \leq x'+y'$ 且 $x-y \geq x'-y'$ 的 $(x',y')$ 是否存在。

这相当于，在平面内插入若干个点 $(x_i+y_i,x_i-y_i)$，然后对于一个查询，我们需要判断 $x+y$ 的后缀的最小值是否不超过 $x-y$。

可以对数据离散化，通过线段树不难维护。$N$ 型三角形同理不再赘述。

以上的操作可以使用 $2$ 棵线段树解决。

首先，如果一个点被覆盖，这个点就不会统计进答案中了。

因此，对于每一次插入，我们需要统计这个三角形能够覆盖多少个点即可，并将被覆盖的点删除。

如果当前想要插入 $W$ 型三角形（顶点是 $(x',y')$），根据以上的结论，我们需要删除满足 $x+y \leq x'+y'$ 且 $x-y \geq x'-y'$ 的全部的点 $(x,y)$。

根据以上的讨论，这相当于在一个前缀中删除全部纵坐标大于 $x'-y'$ 的所有点。

可以在每一个线段树上的叶子结点开一个 std::set 来维护，同时维护区间最大值。

如果一个区间最大值 $\geq x'-y'$，说明这个区间一定存在一个点需要被删除，在线段树上找到所有需要删除的点并逐个删除即可。

由于每一个元素只会加入一次并删除一次，所以这个部分的时间复杂度仍然是 $O(n \log n)。$$N$ 型三角形同理不再赘述。

同样的，以上的操作也可以使用 $2$ 棵线段树解决。

注意：第一部分和第二部分是独立的两个部分，因为，一个点被删除，并不代表这这个点所代表的三角形能够删除，可能会导致没有覆盖覆盖到本应能够覆盖到的点。

时间复杂度 $O(n \log n)$。

提交记录。