题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6059
题意：
给你一组数，让你在其中找到多少个三元组，ai，aj，ak满足ai^aj<=aj^ak。
解：
我们需要判定ai^aj<=aj^ak的话，那么ai和ak的前t-1位都相等的话，第t位不相等时，只有ai[t]==aj[t]，ak[t]!=aj[t]时成立。
那么我们利用字典树进行储存数据，然后记录每个数的相同的位数以及最高不同位，进行每位不相同出现的次数。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int maxn=5e5+10; const int node=maxn*31; int cnt[31][2],num[30]; long long ext=0,ans; int size; struct Tree{ int son[2]; int cnt,ext; }tree[node]; int a[maxn]; typedef long long ll; void cal(int tmp,long long c){ ans+= tree[tmp].cnt*1ll*(tree[tmp].cnt-1)/2; ext+=(c-tree[tmp].cnt)*1ll*tree[tmp].cnt-tree[tmp].ext; } void insert(int x) { int tmp=0; for(int i=0;i<30;i++) { if(!tree[tmp].son[num[i]]){ tree[tmp].son[num[i]]=++size; } if(tree[tmp].son[1-num[i]]) { cal(tree[tmp].son[1-num[i]],cnt[i][1-num[i]]); } tmp = tree[tmp].son[num[i]]; tree[tmp].cnt++; tree[tmp].ext += cnt[i][num[i]] - tree[tmp].cnt; } return ; } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(tree,0,sizeof(tree)); memset(cnt,0,sizeof(cnt)); size=0,ans=0,ext=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); int tmp = a[i]; for(int j=29;j>=0;j--) { num[j] = tmp%2; cnt[j][tmp%2]++; tmp/=2; } insert(i); } printf("%lld\n",ans+ext); } return 0; }