链接：http://acm.hdu.edu.cn/showproblem.php?pid=6059
题意：给你一个数列，找出i<j<k且a[i]^a[j]<a[j]^a[k]的三元组个数；
思路：字典树；
可以知道，如满足以上关系，就是要找出a[i]和a[k]第一位不同的位，另a[j]的这一位与a[I]相同即可，那么就分为两种情况：
（1）a[i],a[j],a[k]的前t-1位都相同，那么对答案的贡献就是d[Fson].num*(d[Fson].num-1)/2;
这里Fson是当前位的兄弟节点，a[i],a[j]都在这个子树中，显然，必然有一大一小两个a[i],a[j]来满足；
（2）a[i],a[k]的前t-1位都相同，a[j]不同，这里a[j]的前t-1为其实是什么不重要，所以加上第一种情况刚好是全部解，对答案的贡献为：
d[Fson].num*(cnt[k][1-t]-d[Fson].num)-d[Fson].ng
后面减去的是不合法的，实际上就是i，j的选取问题，d[Fson].num是我想要的i，cnt[k][1-t]-d[Fson].num是我要的j，但是问题是i，j是有先后顺序的
我不能保证我要的j一定都在i的后面出现，但是，我们可以知道当插入一个节点时，如果要把这个节点作为i，前面出现过的节点肯定不能作为j，那么
对于每一个新的i节点，有多少不合法的呢，是cnt[k][t]-d[z].num;这也很好理解，因为我们知道（2）中i和j不会再同一子树中，那么cnt[k][t]-d[z].num就是
当前位相同的总数减去当前子树的数量，得到的就是，非同一子树中同位相同的比当前节点早插入的节点，即上面说的非法节点；
代码：
#include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long LL; const int MAXN=2e5+5; struct Node { int num,ng,son[2]; }d[31*MAXN]; LL ans=0; int sz,cnt[31][2]; inline void cle(int x) { d[x].son[0]=d[x].son[1]=d[x].num=d[x].ng=0; } void add(int n,int k) { int z=0; //插入时当前节点 while(k>=0) { int t=n>>k&1;//插入数当前位 int &Fson = d[z].son[1-t]; //这里用引用是因为要更新原始数据 int &Tson = d[z].son[t]; if(Fson)//如果我的兄弟节点存在，操作 { ans+=1LL*d[Fson].num*(d[Fson].num-1)/2;//i,j,k前t-1位都相同 ans+=1LL*d[Fson].num*(cnt[k][1-t]-d[Fson].num)-d[Fson].ng;//i,k前t-1位相同，j不一定相同,之所以减掉不成立的，是因为i,j是要有一个顺序 } if(Tson)//如果下一位的节点存在，直接顺延下去 { z=Tson; } else//如果下一位的节点，不存在，创建个新节点，并初始化 { z=Tson=++sz; cle(z); } d[z].num++; cnt[k][t]++; d[z].ng+=cnt[k][t]-d[z].num; k--; } } int main() { //freopen("input.txt","r",stdin); int T,n,x; for(scanf("%d",&T);T;T--) { memset(cnt,0,sizeof cnt); scanf("%d",&n); ans=0,sz=0; cle(0); while(n--) { scanf("%d",&x); add(x,30); } printf("%lld ",ans); } return 0; }