自动搬运

查看原文

来自洛谷，原作者为

	Miracle_InDream 本号已于 2025-08-23 申请禁言。尽量不要 QQ 因为电脑 QQ 上不去懒得弄了只能平板看消息，微信因为没死透还算能用。小号：Carmota_Yumo（小号不到 50 粉的悲哀……）

搬运于2025-08-24 23:03:31，当前版本为作者最后更新于2024-09-07 23:07:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能没人能想到我这只蒟蒻会来写这题题解吧。

赛时打了个暴力（因为太菜了），只拿了 13pts。赛后求助机构老师，老师给出了代码，我自己边打边研究了下，有些没写注释的地方我自己看懂了。感谢老师的指导！

因为数据量比较大，$O(n^2)$ 的时间复杂度肯定会超。

那我们该怎么办呢？

想让 $x \oplus y > \max(x,y)$（注：$\oplus$ 代表异或），那么 $x$ 的最高位 $1$ 一定对应 $y$ 位置的 $0$ ，所以统计最高位的 $1$ 和每个位置的 $0$，再使用排列组合实现。（注：这篇题解所有最高位的 $1$ 和每一位的 $0$ 都是二进制下的！别搞错了！！！！！）

所以，每输入一个数，我们都需要求这个数最高位的 $1$ 和每一位的 $0$。

这一部分的代码如下：

void find1(int x,int v)
{
	int a=1;
	int n=-1;
	while(x)//如果 x>0，那就判断 x 的最后一位是不是 1
	{
		if((x&1)==1)//如果是，n 就变成 a
		{
			n=a;
		}
		a++;
		x>>=1;
		//a 增加 1，x>>=1 的效果与 x/=2 差不多，部分童鞋可以检查下这部分是不是脑子混掉然后直接写上 x/=10 捏~
	}
	b1[n]+=v;//b1[n] 要加上 v。
}//查找最高位的 1。
void find0(int x,int v)
{
	int a=1;
	while(x)//如果 x>0，那就判断 x 的最后一位是不是 0 
	{
		if((x&1)==0)//如果是，b0[a] 就要加上 v。
		{
			b0[a]+=v;
		}
		a++;
		x>>=1;
	}
}//查找每一位的 0。
//这段虽然和上面那个查找最高位的 1 差不多，但是功能上还是有差异的。这个是查找每一位的 0 的。

下面的主函数实现方式也很简单，我们可以边输入边统计最高位的 $1$ 和每一位的 $0$，然后每次询问（更改）都要清空数组里与原数字相应的位置，再统计新数字最高位的 $1$ 和每一位的 $0$（有点儿啰嗦，其实写到这里我自己满脑子也都是最高位的 $1$ 和每一位的 $0$ 了 hhh）。

上代码（除了老师的注释，我自己也加了很多注释，有很多关于自己对代码的解读，如果有问题，可以帮我纠正捏~）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long b1[105],b0[105],a[N],n,q;
long long ans;
void find1(int x,int v)
{
	int a=1;
	int n=-1;
	while(x)//如果 x>0，那就判断 x 的最后一位是不是 1
	{
		if((x&1)==1)//如果是，n 就变成 a
		{
			n=a;
		}
		a++;
		x>>=1;
		//a 增加 1，x>>=1 的效果与 x/=2 差不多，部分童鞋可以检查下这部分是不是脑子混掉然后直接写上 x/=10 捏~
	}
	b1[n]+=v;//b1[n] 要加上 v。
}//查找最高位的 1。
void find0(int x,int v)
{
	int a=1;
	while(x)//如果 x>0，那就判断 x 的最后一位是不是 0 
	{
		if((x&1)==0)//如果是，b0[a] 就要加上 v。
		{
			b0[a]+=v;
		}
		a++;
		x>>=1;
	}
}//查找每一位的 0。
//这段虽然和上面那个查找最高位的 1 差不多，但是功能上还是有差异的。这个是查找每一位的 0 的。
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		find1(a[i],1);
		find0(a[i],1);
		//这里可以边输入边找最高位的 1 和每一位的 0。
	}
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		find1(a[x],-1);
		find0(a[x],-1);
		find1(y,1);
		find0(y,1);
		a[x]=y;
		//因为 a[x] 被更改了，所以这里需要清掉 b1 和 b0 两个数组原本因为 a[x] 造成的改变，并重新统计 y 的最高位的 1 和每一位的 0，存进 b1 和 b0。
		ans=0;
		for(int i=1;i<=32;i++)
		{
			ans+=b1[i]*b0[i];//求修改后数组中合法二元组的个数。
		}
		cout<<ans<<endl;//输出！
	}
	return 0;//华丽结束~~~
}

求管理大大通过捏~