题解 | #小苯的九宫格#

利用前缀和的思想，用所有结果小于 的子数组个数 - 所有结果小于的子数组个数，即为答案。

发现这个 刚好只有一位，要结果小于它，则必须满足在二进制中 ~ 位中不能有 。 根据题目条件，满足不能有 即这个子数组元素在 ~ 位的每一位不能同时存在 和 。

靠赛时没调出来。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    i64 n, k1, k2;
    cin >> n >> k1 >> k2;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    auto solve = [&](int x) -> i64 {
        i64 ans = 0, cnt = 0;
        for (int i = 1; i <= n; i ++ ) {
            bool ok = true;
            for (int j = x; j <= 60; j ++) {
                int u = a[i] >> j & 1;
                int v = a[i - 1] >> j & 1;
                if (u != v) {
                    ok = false;
                }
            }
            if (ok) {
                cnt ++;
            } else {
                ans += cnt * (cnt + 1) / 2;
                cnt = 1;
            }
        }
        ans += cnt * (cnt + 1) / 2;
        return ans;
    }; 

    cout << solve(k2) - solve(k1) << "\n";

    return 0;
}