自动搬运

查看原文

来自洛谷，原作者为

	JohnVictor 云OIer

搬运于2025-08-24 22:21:56，当前版本为作者最后更新于2020-05-21 21:03:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

放上官方题解。

令序列长 $m=2^n$。

首先对于前 $5\%$ 的数据可以直接暴力。复杂度 $O(mq)$。

暴力枚举子集的方法是（这里是 c++ 代码）

int f=x^y;
for(int t=x^y;t>=0;t=(t-1)&f)

当然还有什么都不发生的情况，也就是不存在满足要求的 $c$。这个可以使用 a and b=a 进行特判。

继续开始思考后面的部分分。之后都假设所有的修改和询问都是有效的，也就是 a and b=a一直成立。

这个修改、询问的形式类似一个区间，那么需要知道一个前置知识 高维前缀和。如果不知道的话可以学一下，比较简单。

那么类比不带修直接求区间的和，我们考虑用几个高维前缀和相加减去表示一个询问的答案。

这里可以从简单的情况开始考虑。如果 $a=0$，那么就直接是一个高维前缀和的答案；那么继续考虑，令 $sum(i)$ 为 $i$ 的高维前缀和，如果 $a=1$，那么询问 $(a,b)$ 的答案是一些 $a_c$ 的和，其中 $c$ 是奇数并且 c and b=b。那么这个答案比 $sum(b)$ 小了 $c$ 是偶数，并且 c and b=b 的位数之和。后面的那个恰好可以用 $sum(b-1)$ 表示。

思路逐渐明朗起来，如果 $x$ 是 $b$ 与 $a$ 相同且二进制位 1 的一位的值，那么我们可以得到

$$query(a,b)=query(a-x,b)-query(a-x,b-x)$$

这个式子可以位运算进行优化，x=a&-a，a-x 可以用 a^x 表示。

这个看似还没啥用——如果 $a,b$ 相同那么这个复杂度还是 $m$ 级别的。但是仔细分析：

如果 $a,b$ 二进制不同的位有 $x$ 位，相同的有 $y$ 位，其中 $x+y=n$，那么直接暴力计算就可以用 $O(2^x)$ 次计算完成；如果用上面那种方法，它的复杂度是 $O(2^y)$。

进行特判并且选择可以做到 $O(2^{\min(x,y)})$，也就是 单次询问 $O(\sqrt m)$。这个算法可以通过第二档部分分。

这里有一个很小的优化，没什么用：

可以快速预处理出 $0$ 到$(2^n-1)$ 中每一个数有多少个二进制 1，这样查询二进制 1 的个数就从 $O(\log m)$ 变成了 $O(1)$。具体实现和 FFT 中的那个 rev 数组类似：

for(int i=0;i<(1<<n);i++)count[i]=count[i>>1]+(i&1),rev[i]=(1<<n)-i-1;

其实这么进行修改也是 $O(\sqrt m)$ 的，但是唯一的问题就是无法及时更新。如果询问都在修改后面，可以考虑懒标记，用数组 curr 记录。如果 curr[i] 记录了值，那么就代表所有 i 的子集都要加上这个值。

这里用代码更清楚一点：

void modify(int x,int y,uint z)
{
	if(count[x^y]<=n/2)
	{
		int f=x^y;
		for(int t=x^y;;t=(t-1)&f){
			a[t|x]+=z;
			if(t==0)
				break;
          //这一部分是对修改值不多的情况进行暴力
		}
		return;
	}
	if(x==0)
	{
		curr[y]+=z;//如果x=0那么就可以直接打上懒标记
		return;
	}
	int lbt=x&-x;
	modify(x^lbt,y,z);
	modify(x^lbt,y^lbt,-z);//与 query 部分类似的递归
}

等到所有修改结束后可以下放懒标记，暴力下放的复杂度是 $O(3^n)$，总时间复杂度 $O(\sqrt mq+3^n)$，可以通过第三档部分分。

然而这里并不是没有优化的空间了。下放懒标记的过程完全可以看成又一次高维前缀和。

本来的高维前缀和上的值是它的所有子集的和；而这时候需要加的值，是所有以它为自己的懒标记的和。

举个栗子，如果一个数的二进制表示是 001，那么高维前缀和中就是 000,001 的和，在这种情况下要加上 001,011,101,111 这四个懒标记的和。所以这样只用反着来一遍高维前缀和就行了。

为了加速，我预处理了 rev 数组代表一个数二进制取反后的结果，因为这里不能直接用 ~。（这个 rev 不是 FFT 中的 rev）

话不多说上代码：

void update()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
		{
			if(j&(1<<i))
				curr[rev[j]]+=curr[rev[j^(1<<i)]];
		}
  //这里是反着的高维前缀和
	for(int i=0;i<(1<<n);i++)
		a[i]+=curr[i];
	for(int i=0;i<(1<<n);i++)
		pres[i]=a[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
			if(j&(1<<i))
				pres[j]+=pres[j^(1<<i)];
}

其中 pres 是高维前缀和数组。这一次 update 的复杂度是高维前缀和的复杂度 $O(n2^n)$。

好了，各位大佬们看到这里，正解已经呼之欲出了：分块！

我们假设块长为 $s$，一共 $t$ 块。

修改还是正常修改，查询还是正常查询。这里复杂度是 $O(q \sqrt m)$。

查询的时候，唯一的问题就是计算块内贡献。这个可以位运算 $O(1)$ 计算每个贡献，复杂度是 $ms$；每一块的 update 的复杂度是 $O(tn2^n)$，那么我们可以得到总的复杂度可以达到 $O(m \sqrt {nq}+q \sqrt m)$，在块长为 $\sqrt{nq}$ 时最优。

块内的贡献还是有细节的。大概是这两种情况：

（1）一个修改的数和询问的数没有相同的。

（2）有一部分相同。

这个位运算有很多种实现方法，直接上代码：

for(int i=1;i<=cnt;i++)
			{
				num=(s[i].a|a)&(s[i].b&b);
				if(num==int(s[i].a|a))
				{
					num=(s[i].a|a)^(s[i].b&b);
					ans+=(1<<count[num])*s[i].k;
				}
			}
			cout<<ans<<endl;

std 的长度 2235byte，作为数据结构还是比较良心的。

如果写挂了可以找我要代码，前两天发现有人疑似抄我放的代码，所以不准备直接放。