传送门：HDU6059
题意：给定一个序列a,求有多少个三元组（i，j，k） 满足1<=i<j<k<=n 且 a[i] xor a[j] < a[j] xor a[k]？
思路：
利用字典树维护前 k-1 个数。当前处理第 k 个数。
显然对于 k 与 i 的最高不相同位 kp 与 ip ：
当 ip=0 , kp=1 时，该最高不相同位之前的 ihigher=khigher 。则 jhigher 可以为任意数，均不对 i, k 更高位（指最高不相同位之前的高位，后同）的比较产生影响。而此时 jp 位必须为 0 才可保证不等式 (Ai⊕Aj)<(Aj⊕Ak) 成立。
当 ip=1,kp=0 时， jp 位必须为 1 ，更高位任意。
故利用数组 cnt[31][2] 统计每一位为 0 ，为 1 的有多少个。在字典树插入第 k 个数时，同时统计最高不相同位，即对于每次插入的 p 位为 num[p] (取值 0 或 1)，在同父节点对应的 1-num[p] 为根子树的所有节点均可作为 i 来寻找 j 以获取对答案的贡献。其中又仅要求 jp 与 ip ( ip 值即 1-num[p]) 相同，故 jp 有 cnt[p][ 1-num[p] ] 种取值方案。
但是，同时需要注意 i 与 j 有在 A 数组的先后关系 ( i<j ) 需要保证。故在字典树中额外维护一个 ng 点，记录将每次新加入的点与多少原有点可构成 i, j 关系（注意不是j，i关系）。在后续计算贡献时去掉。
以上转自： 点击打开链接总的思想就是将所有数转化为二进制插到字典树当中去，先枚举A[k]，在将A[k]插入的过程中动态的枚举A[k]和A[i]的最高不同位，然后利用字典树动态的计数，关键是ng的计数不好理解，需要画图体会体会。
代码：
#include<bits/stdc++.h> #define ll long long #define pb push_back #define fi first #define se second #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define rep(i,x,n) for(int i=x;i<n;i++) #define per(i,n,x) for(int i=n;i>=x;i--) using namespace std; typedef pair<int,int>P; const int MAXN = 500010; int gcd(int a,int b){return b?gcd(b,a%b):a;} ll ans; struct node{ int son[2]; int cnt, ng; }Trie[MAXN * 32]; int cnt[32][2]; int dig[32], sz; void calc(int id, int sum) { ans += 1ll * Trie[id].cnt * (Trie[id].cnt - 1) / 2; // 计算a[i]高位和a[j]高位相同的所有可能组合（i<j） ans += 1ll * Trie[id].cnt * (sum - Trie[id].cnt);// 计算a[i]高位和[j]高位不同的所有可能组合(i有可能大于j) ans -= Trie[id].ng;// 去掉i>j的情况 } void insert() { int tmp = 0; for(int i = 0; i < 30; i++) { if(!Trie[tmp].son[dig[i]]) Trie[tmp].son[dig[i]] = ++sz; if(Trie[tmp].son[dig[i] ^ 1]) calc(Trie[tmp].son[dig[i] ^ 1], cnt[i][dig[i] ^ 1]); tmp = Trie[tmp].son[dig[i]]; Trie[tmp].cnt++; Trie[tmp].ng += cnt[i][dig[i]] - Trie[tmp].cnt; } } int main() { int T, n, t; cin >> T; while(T--) { ans = 0; sz = 0; memset(cnt, 0, sizeof(cnt)); scanf("%d", &n); memset(Trie, 0, n * 32 * sizeof(node));//只将可能用到的部分初始化就好了，否则时间增加的飞起 for(int i = 0; i < n; i++) { scanf("%d", &t); for(int i = 29; i >= 0; i--) { cnt[i][t & 1]++; dig[i] = t & 1; t >>= 1; } insert(); } cout << ans << endl; } return 0; }
