题目描述
给定(n)个非负整数数(a_1)，(a_2) , (a_3) (cdots) (a_n)，对于所有 (1<=i<j<=n)，求出(a_i ; xor ; a_j)
求在得到的(n*(n-1)/2)个数
中的前(k)大的和。
对于(30%)的数据，(n<=500)
对于另外(30%)的数据，(0<=ai<=1023)
对于(100%)的数据
(n<=5*10^5,k<=2*10^5,k<=n*(n-1)/2 ,; 0<=ai<=10^9)
时间限制：(2s) 空间限制：(512M)
(30pts)
直接求出任意两个数的xor值 ， 然后丢到数组里排序。
(60pts)
讲真的我也不知道这档部分分怎么拿
难道真是给那些(01Tire)高度只开(10)的人？？？
(100pts)
我是个菜逼，所以我用的是可持久化(01Tire) ， 求第(k)大(O(nlog^2n))
,统计答案(O(nlog^2n)) ， 空间复杂度是(O(nlogn))
通过这种比较劣的方法过了这个题
如果你做过异或粽子那这个题还是蛮好想的(
求异或前(k)大，显然可以通过(O(nlog^2n))的可持久化(01Tire)上二分来求出第k大
但是题目让我们求得是前(k)大异或后和
我们首先考虑一个问题怎么求(01Tire)上一个子树中所有值异或当前值之后的和
考虑一个数组排序后插入可持久化(01Tire) ， 那么在(01Tire)中一个子树必定对应原序列的一个连续子序列
这样我们只要维护每个子树上最小值和子树中数的个数即可
之后处理一颗子树的时候就能在原序列上直接二分找答案然后(O(logn))求出一个子树的贡献
一棵(01Tire)最多有(logn)个贡献 ， 那么(n)棵的话就最多有(nlogn)个贡献，所以最终统计答案的复杂度是(O(nlog^2n))
总复杂度(O(nlog^2n)) (自带巨大常数
所以你(k)开到(10^9)我也是可以做的
代码就不贴了 ， 毕竟是考试题
禁止评论！！！
(End)
其实我异或粽子复杂度是(O(nlog^3n))，所以只有(60pts)，有点遗憾 ， 但这个题其实是比异或粽子更难那么一点的 ， 对我来说还是有必要做一做吧