Give you an array A[1..n]A[1..n]，you need to calculate how many tuples (i,j,k) (i,j,k) satisfy that (i < j < k)(i < j< k) and ((A[i] xor A[j])<(A[j] xor A[k]))((A[i] xor A[j])<(A[j] xor A[k]))
There are T test cases.
1≤T≤201≤T≤20
1≤∑n≤5∗1051≤∑n≤5∗105
0≤A[i]<2300≤A[i]<230 Input There is only one integer T on first line.
For each test case , the first line consists of one integer nn ,and the second line consists of nn integers which means the array A[1..n]A[1..n] Output For each test case , output an integer , which means the answer. Sample Input 1
5
1 2 3 4 5 Sample Output 6
可以很明显得出一个结论 ai和 aj的较高位必须相同 且和 ak不同，的时候所有的组合都是对的。 那么另一种情况 在更高的位里面 ak和 ai的位相同的话，aj不会造成任何影响，那么从高位开始，每次相当于枚举ak的位，把ak的位的影响的贡献算出来，例如到ak的当前位p，那么证明的是在30到 p ai和ak都是相同的 所以aj不造成任何影响，这里可能会有人觉得那结果是不是要加上aj任取得情况，不用，因为其实aj任取的前提是在p位aj要满足有贡献的情况所以 ai与aj在p位相等 是我们要统计的贡献的情况，因为我们枚举的是ak所以不用考虑 ai，aj 找ai aj有两种情况 因为贡献是从高位开始的 所以我们从高位开始枚举 1. ai和aj在同一棵树上 那么结果是 前面的数 这样满足 T[p].cnt*(T[p].cnt-1)/2 除2满足的是i < j 2. 然后第二种情况是 j 在别的子树上 因为aj不规定前面高位都是一样的，前面的j位是随意的 但是还要减去i>j 的情况 只要把每次更新的ak的时候把前面的所有的数都当成是非法的就好 所以就是 T[p].js=num[b][i]-T[p].cnt;
#include <bits/stdc++.h> using namespace std; const int BB = 30; const int N = 5e5+100; struct node { int cnt,js,nxt[2]; }T[N*BB+200]; typedef long long ll; int num[BB][2],go[BB]; ll ans; int sz; void update(int now,int pre) { ans+=(ll)(T[now].cnt*(T[now].cnt-1))>>1; ans+=(ll)(T[now].cnt*(pre-T[now].cnt))-T[now].js; } void insert() { int p=0; for(int i = BB-1;i>=0;i--) { int d=go[i]; if(!T[p].nxt[d]) T[p].nxt[d]=++sz; if(T[p].nxt[1-d]) update(T[p].nxt[1-d],num[i][1-d]); p=T[p].nxt[d]; T[p].cnt++; T[p].js+=num[i][d]-T[p].cnt; } } int main() { int t; scanf("%d",&t); while(t--) { sz=0; ans=0; int n; scanf("%d",&n); memset(T,0,sizeof(T)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++){ int d; scanf("%d",&d); for(int j=0;j<BB;j++) { ++num[j][d&1]; go[j]=d&1; d>>=1; } insert(); } printf("%lld\n",ans ); } }