题目大意

给 $n$n个数的数组 $a$a,问有多少个三元组 $(x,y,z)$(x,y,z)满足 a[x] xor a[y]<a[y] xor a[z]并且 1≤x<y<z≤n

$n\le 50000,1\le a\left[i\right]\le 10^9$n≤50000,1≤a[i]≤109

题解

这种关于异或的题，立马想到了用 $Trie$Trie来做，一个很自然的想法就是枚举中间的 $y$y,然后开两个 $Trie$Trie,一个维护 $1$1到 $y-1$y−1的数位，一个维护 $y+1$y+1到

$n$n的数位，然后同时在两个 $Trie$Trie上 $dfs$dfs。然而这样复杂度会爆掉，我们考虑不直接 $dfs$dfs,而是统计下答案。

设 $cnt\left[i\right]\left[0/1\right]$cnt[i][0/1]表示两颗 $Trie$Trie中，前 $i-1$i−1位相同，第i为不同的个数。 $0$0表示前缀和的 $Trie$Trie中第 $i$i位为 $1$1,后缀和的 $Trie$Trie中第 $i$i位为 $0$0的个数， $1$1反之。

那么我们只需在枚举 $y$y时动态维护 $cnt$cnt即可，统计答案可以直接用 $cnt$cnt来求出。

还有未懂的地方看代码

代码

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年09月22日 星期日 14时48分46秒 *******************************/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=5e4+10;
const int LG=30;
long long ans;
struct Trie{
    int ch[maxn*100][2],tot,sum[maxn*100][2];
    void clear() { memset(ch,0,sizeof ch); memset(sum,0,sizeof sum); tot=1; }
    void insert(int x)
    {
        int c,now=1;
        for(int i=LG;i>=0;i--)
        {
            c=(x&(1<<i))>>i;
            if(!ch[now][c])
                ch[now][c]=++tot;
            sum[now][c]++;
            now=ch[now][c];
        }
    }
    void erase(int x)
    {
        int c,now=1;
        for(int i=LG;i>=0;i--)
        {
            c=(x&(1<<i))>>i;
            sum[now][c]--;
            now=ch[now][c];
        }
    }
}A,B;
int cnt[maxn][2];
void add(int x)
{
    int c,v=1;
    for(int i=LG;i>=0;i--)
    {
        c=(x&(1<<i))>>i;
        cnt[i][c^1]+=B.sum[v][c^1];
        v=B.ch[v][c];
    }
}
void del(int x)
{
    int c,v=1;
    for(int i=LG;i>=0;i--)
    {
        c=(x&(1<<i))>>i;
        cnt[i][c]-=A.sum[v][c^1];
        v=A.ch[v][c];
    }
}
int T,n,a[maxn],c;
int main()
{
    //freopen("xyz.in","r",stdin);
    //freopen("xyz.out","w",stdout);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        A.clear();B.clear();ans=0;
        memset(cnt,0,sizeof cnt);
        for(int i=2;i<=n;i++) B.insert(a[i]);
        for(int i=2;i<n;i++)
        {
            A.insert(a[i-1]); add(a[i-1]);
            B.erase(a[i]); del(a[i]);
            for(int j=LG;j>=0;j--)
            {
                c=(a[i]&(1<<j))>>j;
                ans+=cnt[j][c^1];
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}