A BIT of an Inequality

题目描述

给你一个数组 $a_1,a_2,\dots ,a_n$ 。求这样的图元（ $x,y,z$ ）的个数：

• $1\le x\le y\le z\le n$ , 和
• $f(x,y)\oplus f(y,z)>f(x,z)$ .

我们定义 $f(l,r)=a_l\oplus a_{l+1}\oplus \dots \oplus a_r$ ，其中 $\oplus$ 表示 bitwise XOR。

输入描述

第一行包含一个整数 $t$ ( $1\le t\le 10^4$ ) - 测试用例数。

每个测试用例的第一行包含一个整数 $n$ ( $1\le n\le 10^5$ )。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^9$ )。

保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出描述

对于每个测试用例，在一行中输出一个整数 – 描述的图元的组数。

样例输入

3
3
6 2 4
1
3
5
7 3 7 2 1

样例输出

4
0
16

原题

CF——传送门

思路

显然根据异或运算的交换律，$f(x,y)\oplus f(y,z)>f(x,z)$ 等价于 $f(x,z)\oplus a_y>f(x,z)$。那么，问题就可以转化为对于 $a_1$ 到 $a_n$ 的每个 $a_i$，其与 $f(x,z)$ 进行异或运算是否会使结果变小。如果能使结果变小，则将该方案统计到答案中。而对于异或后对结果的影响，我们只需要考虑 $a_i$ 的最高位的 1，若该位在左式即 $f(x,y)\oplus f(y,z)$ 中的异或结果为 1，则将该方案统计进答案中。

代码

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

const int maxn = 1e5 + 6;
const int maxbit = 30;

// 第i个元素，第j+1个bit位，前缀以及后缀异或结果为k(0或1)
int prefix[maxn][maxbit][2]; // 该条件下 包含第i-1个元素的前缀的个数
int suffix[maxn][maxbit][2]; // 该条件下 包含第i+1个元素的后缀的个数

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        // dp转移
        for (int j = 0; j < 30; j++)
        {
            // 初始化
            prefix[0][j][0] = 0;
            prefix[0][j][1] = 0;
            suffix[n + 1][j][0] = 0;
            suffix[n + 1][j][1] = 0;
            for (int i = 1; i <= n; i++)
            {
                int bit = (a[i] >> j) & 1; // 第j+1个bit位是1或是0
                for (int k = 0; k <= 1; k++)
                {
                    prefix[i][j][k] = (bit == k) + prefix[i - 1][j][k ^ bit];
                }
            }
            for (int i = n; i >= 1; i--)
            {
                int bit = (a[i] >> j) & 1; // 第j+1个bit位是1或是0
                for (int k = 0; k <= 1; k++)
                {
                    suffix[i][j][k] = (bit == k) + suffix[i + 1][j][k ^ bit];
                }
            }
        }
        ll ans = 0; // 统计个数
        for (int i = 1; i <= n; i++)
        {
            int highbit = -1; // 当前元素bit位为1的最高位置
            for (int j = 0; j < 30; j++)
            {
                if ((a[i] >> j) & 1)
                    highbit = j;
            }
            ans += 1LL * prefix[i - 1][highbit][1] * (suffix[i + 1][highbit][0] + 1);
            ans += 1LL * (prefix[i - 1][highbit][0] + 1) * suffix[i + 1][highbit][1];
        }
        cout << ans << '\n';
    }

    return 0;
}