codeforces 742B - Arpa’s obvious problem and Mehrdad’s terrible solution

There are some beautiful girls in Arpa’s land as mentioned before.

Once Arpa came up with an obvious problem:

Given an array and a number x, count the number of pairs of indices i, j (1 ≤ i < j ≤ n) such that , where  is bitwise xoroperation (see notes for explanation).

Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.

First line contains two integers n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) — the number of elements in the array and the integer x.

Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the elements of the array.

Print a single integer: the answer to the problem.

二分搜索

AC代码：

# include <stdio.h>
# include <vector>
using namespace std;
typedef long long int ll;
int a[100010];
vector<int> vec[100010];
int main(){int i, j, k, x, n, temp, s;scanf("%d%d", &n, &x);for(i=1; i<=n; i++){scanf("%d", &a[i]);vec[a[i]].push_back(i);}ll ans=0;for(i=1; i<n; i++){temp=x^a[i];if(temp<100010)s=vec[temp].size();elsecontinue;if(s>0){int it=lower_bound(vec[temp].begin(), vec[temp].end(), i+1)-vec[temp].begin();if(it>s)continue;if(it!=s){ans=ans+s-it;}}}printf("%I64d", ans);return 0;
}