$O(Nloga_i)$

关键观察

1. 不等式转换：

$f(x,y) ⊕ f(y,z) = f(x,z) ⊕ a_y$

因此条件可以转化为：$f(x,z) ⊕ a_y > f(x,z)$

2. 位运算特性：

对于任意数 $a$ 和 $b$ ，$a ⊕ b > a$ 当且仅当 $b$ 的最高位在 $a$ 中对应位为 $0$

解题思路

1. 前缀与后缀预处理：

• 预处理前缀数组 $pre[i][j][0/1]$ ，表示前 $i$ 个元素在第 $j$ 位上异或和为 $0/1$ 的数量

• 预处理后缀数组 $suf[i][j][0/1]$ ，表示从 $i$ 到 $n$ 的元素在第 $j$ 位上异或和为 $0/1$ 的数量

2. 统计方法：

• 对于每个元素 $a[i]$，确定其最高位 $t$

• 统计满足 $f(x,z)$ 的第 $t$ 位为 $0$ 的 $(x,z)$ 对数量

• 使用预处理的前缀和后缀数组快速计算

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 30;

int a[N];
LL pre[N][M][2], suf[N][M][2];

void solve()
{
    int n;
    cin >> n;
    // 预处理前缀数组
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        for(int j = 0; j < M; j ++)
            if((a[i] >> j) & 1) // 当前位为1
            {
                pre[i][j][1] = pre[i - 1][j][0] + 1;
                pre[i][j][0] = pre[i - 1][j][1];
            }
            else // 当前位为0
            {
                pre[i][j][1] = pre[i - 1][j][1];
                pre[i][j][0] = pre[i - 1][j][0] + 1;
            }
    }
    
    // 预处理后缀数组
    for(int i = 0; i < M; i ++)
        suf[n + 1][i][0] = suf[n + 1][i][1] = 0;
    for(int i = n; i; i --)
        for(int j = 0; j < M; j ++)
            if(a[i] >> j & 1)
            {
                suf[i][j][1] = suf[i + 1][j][0] + 1;
                suf[i][j][0] = suf[i + 1][j][1];
            }
            else
            {
                suf[i][j][1] = suf[i + 1][j][1];
                suf[i][j][0] = suf[i + 1][j][0] + 1;
            }
            
    LL ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x = a[i];
        int t = -1;
        // 找到最高有效位
        while(x)
        {
            x >>= 1;
            t ++;
        }
        
        // 统计满足条件的(x,z)对
        int l0 = pre[i][t][0], l1 = pre[i][t][1];
        int r0 = suf[i + 1][t][0], r1 = suf[i + 1][t][1];
        ans += l0 * (LL)r0 + l1 * (LL)(r1) + pre[i - 1][t][1];
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t --)
        solve();
}