[Editorial] Codeforces Contest 878D

中文题面

好题，写篇题解记录一下。

首先如果值域是 \(\{0,1\}\)，那么直接搞一个bitset维护一下。由于只有 \(2^k\) 中不同的初始取值，所以维护 \(2^k\) 长度即可。

然后考虑值域比较大的时候，直接枚举答案。把 \(<\) 的都设成 \(0\)，其余设成 \(1\)。那么从大到小枚举，第一个是 \(1\) 的部分就是答案的排名。

同理，这个也只有 \(2^k\) 种取值，所以直接做的复杂度还是 \(O(\dfrac{q2^k}{w})\)。