Kanade's trio

                                                                   Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)                                                                                              Total Submission(s): 854    Accepted Submission(s): 308 Problem Description Give you an array  A[1..n] ，you need to calculate how many tuples  (i,j,k)  satisfy that  (i<j<k)  and  ((A[i] xor A[j])<(A[j] xor A[k])) There are T test cases. 1≤T≤20 1≤∑n≤5∗105 0≤A[i]<230   Input There is only one integer T on first line. For each test case , the first line consists of one integer  n  ,and the second line consists of  n  integers which means the array  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   Source 2017 Multi-University Training Contest - Team 3  

题意：给出一个序列，问有多少三元组满足（a[i]^a[j]）<（a[j]^a[k]）（i<j<k）

解题思路：可以枚举数字每一位考虑，建一棵记录前缀的字典树，sum记录这个节点添加的个数，x代表不符合要减去的个数，tot[i][j]代表第i位的j（j=0,1）当前数量。

枚举ak的每一位，对于ak的第t位（记作ak[t]）,如果ak[t]==1，那么对答案产生贡献的ai[t]和aj[t]必然为0，而且ai[0]~ai[t-1]必然和ak[0]~ak[t-1]对应相等。记ak[t]对应地节点为pp，与其同父亲的另一个节点为p。

ai[0]~ai[t-1]和ak[0]~ak[t-1]和aj[0]~aj[t-1]全都相等时，ak[t]加入后，贡献为sum[p]*(sum[p]-1)/2

ai[0]~ai[t-1]和aj[0]~aj[t-1]有部分不相等，ai[0]~ai[t-1]和ak[0]~ak[t-1]全都相等时时，贡献为sum[p]*(tot[i][1-b[i]]-sum[p])-x[p]，这时会出现不合法的情况，所以要减去

x[p]的话，每次加入一个点，那么这个点必然会在当前节点产生tot[i][b[i]]-sum[pp]不合法的贡献

如果ak[i]==0答案也类似可以得到

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; int a,b[35],n; int cnt,sum[500009*35],nt[500009*35][2],tot[35][2]; LL ans,x[35*500009]; void Insert() { int k=0; for(int i=0; i<31; i++) { if(!nt[k][b[i]]) { nt[k][b[i]]=++cnt; memset(nt[cnt],0,sizeof nt[cnt]); x[cnt]=sum[cnt]=0; } int p=nt[k][1-b[i]],pp=nt[k][b[i]]; ans+=1LL*sum[p]*(sum[p]-1)/2; ans+=1LL*sum[p]*(tot[i][1-b[i]]-sum[p])-x[p]; x[pp]+=tot[i][b[i]]-sum[pp],sum[pp]++,tot[i][b[i]]++; k=nt[k][b[i]]; } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); cnt=ans=x[0]=sum[0]=0; memset(tot,0,sizeof tot); memset(nt[0],0,sizeof nt[0]); for(int i=1; i<=n; i++) { scanf("%d",&a); for(int j=30; j>=0; j--) b[j]=a&1,a>>=1; Insert(); } printf("%lld\n",ans); } return 0; }