挑战赛 81 F

给一个有向图，每次询问编号在一个区间内的点及其能到达的点的点权构成的集合的 。

满足询问以以下方式随机：

• 确定一个 ，区间在所有包含 的区间中均匀随机。

，。10s。

值域是假的，实际上是 。

有一个赤石暴力做法，考虑对区间长度数据分治：

• 若区间长度 ，那么根据随机，每次区间长度 的概率时 （当 时）。此时每次暴力 ，认为 同阶，复杂度 即 。
• 若区间长度 ，我们采用扫描线的方法。
  • 先暴力 bitset 求出每个颜色对应在序列上的位置，颜色 第 个位置 表示从点 能走到一个权值为 的点。然后我们把一个颜色的所有极长的 的段拿出来，一个段 ，如果对于查询的 ，那么这个颜色不在这个区间内。
  • 因为我们查询区间长度是 的，所以我们只保留长度至少为 的极长段。这样总段数只有 。
  • 这个是类似第 大问题，考虑二分或者值域分块。我们考虑二分，之后的问题变成每个颜色有 ，每个询问有 ，数 的方案数，乍一看是三维偏序，套上二分是三个老哥，实际上我们二分实在其中一维偏序上，可以在扫描线维护 ，外层线段树维护 ，内层线段树维护 ，然后每次查询在满足 的 个线段树上一起二分，那么复杂度就可以做到 。其中 是操作数，也就是 。所以这部分复杂度

取 ，复杂度 。