【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)$ 了。