hdu 6059 | 2017 Multi-University Training Contest - Team 3 Kanade's trio (trie)
http://acm.hdu.edu.cn/showproblem.php?pid=6059
题意：
含 N 个数字的 A 数组，求有多少个三元组 (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k]
思路:
考虑a[i]和a[k]二进制不同位中的最高位，此时满足题意的a[j]是该位与a[i]相同，其他位任意的所有a[j]的个数。
我们可以从1..n，依次插入a[k]到trie中,插入时，顺便用num[i][j]统计二进制第i位为j的数的个数。
当要插入a[k]时，a[1]..a[k-1]已经插入到了trie中。
trie上统计当某个节点，该位为0的数的个数和该为为1的数的个数。
需要注意这样统计出的数并不能保证i<j (但是可以保证i<k。。。)
因为我们的trie需要额外维护一部分ext.具体解释见代码注释。
/* ***********************************************
Author :111qqz
Created Time :2017年11月12日 星期日 01时30分29秒
File Name :6059.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=5E5+7;
7int a[N];
8int num[35][2];//cnt[i][j] 表示二进制表示中第i位为j的数的个数
9struct Trie
10{
11 struct Node
12 {
13 Node *nxt[2];
14 LL cnt[2];//需要统计前缀为某个串，该位置为0和该位置为1的个数。
15 LL ext[2];
16 Node()
17 {
18 for ( int i = 0 ; i < 2; i++) nxt[i] = NULL;
19 cnt[0]=cnt[1]=0 ;
20 ext[0]=ext[1]=0;
21 }
22 };
23 Node *root;
24 void init()
25 {
26 root = new Node();
27 }
28 Trie()
29 {
30 root = new Node();
31 }
32 void Insert(int x)
33 {
34 Node *u = root;
35 for ( int i = 29 ; i >= 0 ; i--)
36 {
37 int y = (x>>i)&1;
38 num[i][y]++; //统计二进制第i位为y的数的个数
39 u->cnt[y]++; //统计trie树上当前节点数的个数
40 u->ext[y]+=num[i][y]; //把此时插入的数看做a[i]，那么u->ext[y]就是满足j<=i 的j的数目
41 //因为之后要用到，所以要提前维护
42 if (u->nxt[y]==NULL) u->nxt[y] = new Node();
43 u = u->nxt[y];
44 }
45 }
46 LL Cal( int x)
47 {
48 Node *u = root;
49 LL res = 0 ;
50 for ( int i = 29 ; i >= 0 ; i--)
51 {
52 int y = (x>>i)&1;
53 res += num[i][y^1]*u->cnt[y^1]-u->ext[y^1];
54//对于此时插入的a[k]的二进制第i位（从低往高）的数y,只有当a[i]和a[j]的第i位为1-y时，才会贡献答案。
55 // num[i][y^1]为第i位为1-y的a[j]的个数（a[j]的其他位，包括比i高的位和比i低的位都不受限制
56 // u->cnt[y^1]表示trie树上，从rt到p节点所表示的二进制位上，a[i]与a[k]一直相同，p的下一个节点a[i]与a[k]的二进制位不同 的 a[i]的个数
57 u = u->nxt[y];
58 if (u==NULL) break;
59 }
60 return res;
61 }
62}trie;
63void solve()
64{
65 trie.init();
66 ms(num,0);
67 LL ans = 0 ;
68 int n;
69 scanf("%d",&n);
70 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
71 for ( int i = 1 ; i <= n ; i++)
72 {
73 ans = ans + trie.Cal(a[i]);
74 trie.Insert(a[i]);
75 }
76 cout<<ans<<endl;
77}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 int T;
7 cin>>T;
8 while (T--) solve();
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}