CF1260D A Game with Traps

你正在玩一款电脑游戏，带领着一支由 $m$ 名士兵组成的小队。每名士兵都有一个敏捷值 $a_i$。 你要通过的关卡可以表示为一条从 $0$ 点（你和小队的初始位置）到 $n+1$ 点（Boss 所在位置）的直线段。 关卡中布满了 $k$ 个陷阱。每个陷阱由三个数字 $l_i$、$r_i$ 和 $d_i$ 表示。$l_i$ 是陷阱的位置，$d_i$ 是陷阱的危险等级：当某个敏捷值小于 $d_i$ 的士兵踩到陷阱（即移动到 $l_i$ 点）时，他会立刻被杀死。幸运的是，你可以拆除陷阱：如果你移动到 $r_i$ 点，你就可以拆除这个陷阱，此后它对你的士兵不再有威胁。陷阱不会影响你，只会影响你的士兵。 你有 $t$ 秒的时间完成关卡——也就是要在 $t$ 秒内把你选择的一些士兵带到 Boss 那里。在关卡开始前，你可以选择哪些士兵随你出发，哪些不随你出发。之后，你必须把所有被选中的士兵带到 Boss 那里。为此，你可以执行以下操作： - 如果你当前在 $x$ 位置，你可以移动到 $x+1$ 或 $x-1$。这个动作消耗 1 秒； - 如果你当前在 $x$ 位置，并且你的小队也在 $x$ 位置，你可以带着小队一起移动到 $x+1$ 或 $x-1$，用时 1 秒。只有当移动后不会让任何士兵处于危险中（即小队要移动到的位置没有未被拆除且 $d_i$ 大于某士兵敏捷值的陷阱）时，才能执行此操作； - 如果你当前在 $x$ 位置，且存在陷阱 $i$ 满足 $r_i = x$，你可以拆除这个陷阱。这个动作是瞬时完成的（不消耗时间）。 注意，每次操作后，你和小队的位置都必须是整数。 你需要选择最多的士兵，使得能在不超过 $t$ 秒内把他们全部带到 $n+1$ 点（Boss 所在位置）。

第一行包含四个整数 $m$、$n$、$k$ 和 $t$（$1 \le m, n, k, t \le 2 \cdot 10^5$，$n < t$），分别表示士兵数量、你与 Boss 之间的整数点数量、陷阱数量和你能用的最大秒数。 第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$1 \le a_i \le 2 \cdot 10^5$），其中 $a_i$ 表示第 $i$ 个士兵的敏捷值。 接下来 $k$ 行，每行包含三个整数 $l_i$、$r_i$ 和 $d_i$（$1 \le l_i \le r_i \le n$，$1 \le d_i \le 2 \cdot 10^5$），分别表示陷阱的位置、可以拆除陷阱的位置和陷阱的危险等级。

输出一个整数，表示你最多可以选择多少名士兵，使得能在不超过 $t$ 秒内把他们全部带到 Boss 那里。

在第一个样例中，你可以带敏捷值为 $3$、$4$ 和 $5$ 的士兵。行动方案如下： - 独自前往 $2$； - 拆除陷阱 $2$； - 独自前往 $3$； - 拆除陷阱 $3$； - 独自返回 $0$； - 带着小队一起前往 $7$。 整个计划可以在 $13$ 秒内完成。 由 ChatGPT 4.1 翻译