自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:16:26，当前版本为作者最后更新于2025-05-28 15:35:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

高一的时候我们教练往 CSP 模拟赛里扔了一个这样的题：

给定一个长度为 $10^5$ 的，值域在 $[0,2^{18})$ 中的数组 $a$。每次给定 $(x,v)$，求出最小的 $i \ge x$，使得 $a_i \text{ and } v=0$。

当时就整出了一个这样的做法：从后往前扫描 $x$。查询的时候将 $v$ 取反，即要求 $a_i \subseteq v$。

然后有两种做法：插入 $a_i$ 的时候，暴力扫描其所有超集；或者询问 $v$ 的时候，查询其所有子集。

发现这样询问和修改必须有一个是 $O(1)$ 有一个是 $O(V)$。考虑根号分治，对于后 $9$ 位做一种算法，对于前 $9$ 位做另一种算法。即在 $O(n \sqrt V)$ 的复杂度内解决了这个题。

回到这道题，我们现将 $a_i=0$ 的位置剔除。直接做 $O(nb)$ 次询问。

每次询问，我们先找到一个 $a_i$ 使得 $a_i \text{ and } x =0$。然后 $x \leftarrow x \text{ or } a_i$。不断重复此过程。

显然我们找到的 $i$ 一定是递增的，符合题目要求。而在 $b$ 次操作后此过程一定会终止。

所以说，我们这时候有 $n$ 次修改，$nb^2$ 次查询。那么很容易平衡到 $O(nb \sqrt{2^b})$。

最短解，跑得也挺快。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXM=(1<<20)+10;
int n,b,a[MAXN],vis[MAXM],l;
ll sum,ans[MAXN];
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>b,l=min(b,14);
	ffor(i,1,n) cin>>a[i];
	roff(i,n,1) {
		if(!a[i]) sum+=i;
		else {
			int dt=(1<<l)-1-(a[i]&((1<<l)-1)),ot=(((a[i]>>l)+1)<<l)-1;
			for(int s=dt;s;s=(s-1)&dt) vis[ot-s]=i;
			vis[ot]=i;
		}
		ans[i]=b*sum;
		ffor(j,0,b-1) {
			int ot=(1<<b)-1-(1<<j);
			while(1) {
				int x=(ot>>l)<<l,y=ot-x,nxt=n+1;
				for(int s=x;s;s=(s-1)&x) if(vis[s+y]) nxt=min(nxt,vis[s+y]);
				if(vis[y]) nxt=min(nxt,vis[y]);
				if(nxt==n+1) break ;
				ans[i]+=nxt,ot-=a[nxt];
			}
		}
	}
	ffor(i,1,n) cout<<ans[i]<<' ';
	return 0;
}