异或不等式？ 01trie的深入理解·

1.序列a，从a1,a2,a3，……an,求二元组(i,j)，i<j,满足a[i]^a[j]>=k的个数。

思路每次固定j，然后求所有i<j,a[i]^a[j]>=k的个数。

如何处理呢？

异或问题可以先考虑使用01trie。

01trie维护的是一个区间内所有数的二进制拆分序列，特点是从高位往低位拆分。

在这题中a[j]与k都是已知的,然后让a[j]进01trie中跑二进制分解，设k当前位为p,a[j]当前位是s，如果p==1时,只能往s^1的方向走才能保持相等，如果p==0时，可以往s的方向走也可以往s^1的方向走，为了保证答案的完整性，要往s的方向走,这样能保证当前位与p相等，并且要加上往s^1的方向走的结果，因为这个是当前位大于p的数的集合。走到最后要加上与其完全相等的点的答案。

2.链接：https://ac.nowcoder.com/acm/contest/47931/J
来源：牛客网
求ai^bj>aj^bi，且i<j的二元组个数？
思路：一般是想办法把和 i,j 有关的项分离开，如何保证分离之后结果不变呢？按位分离

考虑对于每一位，将 （ai,bi) 视为一个二元组，重新定义比较关系：

        （0，0)==(1,1)  （1,0）==（0,1）

 （0，0）>(0,1)    (1,1) >(1,0)   (1,0) >(0,0)   (0,1)>(1,1)

所有01trie 路径节点记录的是（ai^bi)的值，w[节点][0/1]记录的是bi==0或bi==1的节点的个数。

然后就是从高位到低位分解，进行i点的二元组与区间数的二元组之间比较，获得最后答案。

原文地址：http://www.cnblogs.com/ljl1234/p/16920304.html