题目描述

难度分:$1200$

输入$T(\leq 10)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

输出有多少对$(i, j)$，满足$i \lt j$且$(a[i] \land a[j]) \geq (a[i] \oplus a[j])$。

输入样例

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

输出样例

1
3
2
0
0

算法

排序+二分

先将$a$数组排序，然后开始枚举其中的较小值$a[i]$（也可能数对中两个数都相等，相等是肯定满足$(a[i] \land a[j]) \geq (a[i] \oplus a[j])$的）。

然后我做了个猜测，对于$\geq a[i]$的$a[j]$，如果$a[j]$是第一个不满足$(a[i] \land a[j]) \geq (a[i] \oplus a[j])$的数值，那么$\geq a[j]$的数值$v$肯定也不会满足$(a[i] \land v) \geq (a[i] \oplus v)$。尝试造了几个例子，发现这个规律很对，就直接二分查找最后一个满足$(a[i] \land a[j]) \geq (a[i] \oplus a[j])$的$j$了，那么以$a[i]$为较小值且满足条件的数对就有$j-i$个，累加在答案上即可。

复杂度分析

时间复杂度

排序的时间复杂度为$O(nlog_2n)$。之后枚举其中一个$i$，二分计算有多少个$j$满足$(a[i] \land a[j]) \geq (a[i] \oplus a[j])$，因此每个$i$都要$O(log_2n)$计算对答案的贡献，整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的数组$a$，空间消耗主要就是排序时的空间复杂度，以快排为基准，空间复杂度为$O(log_2n)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int t, n, a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        long long ans = 0;
        for(int i = 1; i < n; i++) {
            int l = i + 1, r = n, j = -1;
            while(l <= r) {
                int mid = l + r >> 1;
                if((a[i]&a[mid]) >= (a[i]^a[mid])) {
                    j = mid;
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }
            if(j != -1) {
                ans += j - i;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}