YALI集训 异或第p小

Description

给定一个整数序列(a_1, a_2, … ,a_n),其中a_i \in [0,2^k)

定义f(x)为序列(a_1 | x, a_2 | x, … , a_n | x)的逆序对个数,也就是满足i < ja_i | x > a_j | x(i, j)个数。

对所有i \in [0,2^k)从小到大排序,第一关键字为f(i),第二关键字为i。求排在第p位的元素res以及f(res),序列下标从1开始。

阅读更多