【2018icpc Regional 北京 F】【hihocoder1875】The Kth Largest Value

题目大意

  给定一幅 $n$ 个点的有向图,若 $u$ 可达 $v$,则把 $u \oplus v$ 加进一个可重集合里。有 $Q$ 个询问,每次询问求集合里的第 $k$ 大的数。
  $n \le 50000,\ k \le 10^9,\ Q \le 10$

题解

  缩环后每个点 $u$ 可以用 bitset 得到一个 $v$ 的集合。

  想象一下把每个点的贡献(各种 $u \oplus v$)合起来构一棵 trie,那么答案就可以从高位到低位贪心了,能放 1 就放 1 否则放 0 那种。于是问题转化成问某个子树的标记数量。
  但是把 trie 建出来时间复杂度就不对了。贪心了答案的某一位后,我们想知道当前这个范围内的数量,就 $O(n)$ 扫每一个点单独统计。

  对于每个点的询问相当于,给定一个区间,求这个点有多少个可达的点,标号在这个区间内。那就是 bitset 的 count 了。
  但是不能每个点 $O(\frac{n}{32})$ 地询问,否则会 T。所以这个 bitset 要处理一下,比如手写 bitset,每 32 位作为一个单元,求出每个单元的 1 的个数,做前缀和。这样询问每个点的时候,就像分块一样只需要 $O(32)$ 了。