题意分析
我们先思考：什么样的两个 $x,y$，会满足 $x \oplus y>\max(x,y)$。
为了便于表述，令 $x>y$。
举个例子：
| 数值 | $x$ 的最高位 | $y$ 的最高位 | |||
|---|---|---|---|---|---|
| $x$ | $1$ | $0$ | $1$ | $0$ | … |
| $y$ | $1$ | … | |||
| $x\oplus y$ | $1$ | $0$ | $1$ | $\color{red}1$ | … |
见表格中红色的 $\color{red}1$，$x\oplus y$ 中，$y$ 的最高位为 $1$，而在 $x$ 上对应的位置为 $0$，而 $0\oplus 1=1$。
于是，$x\oplus y>\max(x,y)$。
如果 $y$ 的最高位（显然，最高位为 $1$）在 $x$ 上的值为 $1$ 呢？
那么这一位在 $x\oplus y$ 上便为 $0$，则显然小于 $x$。
总结：当 $x,y$ 其中一个数的最高位在另一个数的对应位置上为 $0$ 的时候，$x \oplus y>\max(x,y)$。
定义 $t[i][x]$，$i\in[1,n],x\in{1,2}$。
$t[i][0]$ 表示所有 $a[j]$ 在二进制下第 $i$ 位为 $0$ 的数的个数。
$t[i][1]$ 表示所有 $a[j]$ 在二进制下最高位为第 $i$ 位的数的个数。
最终答案即 $\large \sum\limits_{i=1}^{\lfloor\log_2V\rfloor}t[i][0]\times t[i][1]$，其中 $V$ 为值域。
注意开 long long。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const int N=1e6;
int n,q,a[N+1],t[30][2];
void count(int x,int k){//k=-1清除标记
int i=0;
while(x>0){
if(~x&1)t[i][0]+=k;
i++;x>>=1;
}t[i-1][1]+=k;//最高位
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
count(a[i],1);
}
while(q--){
int x,y;
scanf("%d %d",&x,&y);
count(a[x],-1);
a[x]=y;
count(a[x],1);
ll ans=0;
for(int i=0;i<30;i++){
ans+=1ll*t[i][0]*t[i][1];
}printf("%lld\n",ans);
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
