hdu6059

201708

• 字典树。
• 若$A_i~xor~A_j<A_j~xor~A_k$，考虑$A_i$和$A_k$不同的位中最高的，根据这一位的值可以知道$A_j$这一位的值必须是多少。
• 假设当前$A_i$的第$x$位值为$y$，那么$A_j$的$x$位值为$y$，$A_k$的第$x$位值为$1-y$。$A_i$和$A_k$的前$x-1$位相等。
• 如果枚举$A_i$，很容易知道$A_k$的前$x$位是怎样的，并且可以统计$A_k$的个数（在字典树上存信息）。但是无法得知$i...k$之间有多少个$j$满足以上条件。
• $f[a][b][c]$数组存储前$a$个数，第$b$位值为$c$的有多少个。$f[N][30][2]$。
• 在字典树上储存前$k$个的信息，枚举到$i$时，减去即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=500005;
int n;
int a[N],f[N][40][2];
struct Trie {
    int nex[N*40][2];
    int cnt[N*40];
    ll add[N*40];
    int tot,root;
    int newNode() {
        memset(nex[tot],-1,sizeof(nex[tot]));
        cnt[tot]=add[tot]=0;
        return tot++;
    }
    void init() {
        tot=0;
        root=newNode();
    }
    void upd(ll x,int c,int ii) {
        int now=root;
        for(int i=29;i>=0;--i) {
            int v=((x>>i)&1);
            if(nex[now][v]==-1) {
                nex[now][v]=newNode();
            } 
            now=nex[now][v];
            cnt[now]+=c;
            add[now]+=1ll*c*f[ii][i][v^1];
        }
    }
    ll qry(ll x,int ii) {
        ll res=0;
        int now=root;
        for(int i=29;i>=0;--i) {
            int v=((x>>i)&1);
            int ta=add[nex[now][v^1]];
            int tb=cnt[nex[now][v^1]]; 
            res=res+ta-1ll*tb*f[ii][i][v];
            now=nex[now][v];
        }
        return res;
    }
}tr;
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d",&n);
        ///init
        tr.init();
        memset(f,0,sizeof(f));
        ///read 
        rep(i,1,n+1) {
            scanf("%d",a+i);
            for(int j=29;j>=0;--j) {
                ++f[i][j][(a[i]>>j)&1];
            }
        }
        ///get f
        rep(i,1,n+1) {
            rep(j,0,30) {
                rep(k,0,2) {
                    f[i][j][k]+=f[i-1][j][k];
                }
            }
        }
        ///solve
        rep(i,1,n+1) tr.upd(a[i],1,i);
        ll ans=0;
        rep(i,1,n+1) {
            tr.upd(a[i],-1,i);
            ans=ans+tr.qry(a[i],i);
        }
        ///print
        printf("%lld\n",ans);
    }
    return 0;
}