01数组与逆序对题解

可以发现只有全0的子数组满足题设条件。

假设存在某个不全为0的数组满足条件，我们从全0数组开始，去构造出这个数组。假设目前数组长度为n，每当我们插入一个1在位置i时，逆序对最多增加 ,而二进制所表示的数值增加了，显然有 。

于是计算全0子数组数量即可。复杂度 。

#include <bits/stdc++.h>
#define int long long

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];

    int cnt = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1)
            ans += (cnt + 1) * cnt / 2, cnt = 0;
        else
            cnt++;
    }
    ans += (cnt + 1) * cnt / 2;
    std::cout << ans << '\n';
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

bonus：如果你不想思考，也可以注意到逆序对最多为平方级别，在题给数据范围下即 ，于是可以对于每个点往后做35次暴力，也是可以通过的，复杂度 。这个做法可以做顺序对甚至顺序对在线版本。