自动搬运

查看原文

来自洛谷，原作者为

	123456zmy 123456!

搬运于2025-08-24 22:02:12，当前版本为作者最后更新于2020-09-04 19:34:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：
给你一个序列，支持全局加及查询二进制某位为 $1$ 的数的个数，序列中的数对 $65536$ 取模。

设序列中的数的值域为 $v$。

注意到操作都是全局的，所以序列中的数可以开桶来存，全局加也可以用标记解决。

对于查询，需要计入答案的数的区间是 $[k\cdot2^{i+1}+2^i,(k+1)\cdot2^{i+1})$，暴力 $O(mv)$。加个指令集就可以过了，代码。

通过观察发现其答案只与加上的数的和的后 $i$ 位有关，用前缀和及记忆化优化后可以通过此题。可以卡到最优解。

AC代码：（$O(n+v\log v),191ms$）

#include<bits/stdc++.h>
int n,m,a2;
char c;
unsigned short p,x;
int sum[131088],cnt[131088],ans[17][65537];
bool vis[17][65537];
int main()
{
	register long long anss=0;
	register unsigned short p=0;
	scanf("%d%d",&n,&m); 
	for(int i=0;i<n;i++)scanf("%d",&a2),++cnt[a2],++cnt[a2+65536];
	sum[0]=cnt[0];
	for(int i=1;i<131088;i++)sum[i]=sum[i-1]+cnt[i];
	while(m--)
	{
		scanf("%s%d",&c,&x);
		if(c=='A')p+=x;
		else
		{
			if(vis[x][p&((2<<x)-1)])anss+=ans[x][p&((2<<x)-1)];
			else
			{
				register int ansa=0;
				for(register int i=(2<<x)-1;i<65536;i+=2<<x)ansa+=sum[65536-p+i]-sum[65536-p+i-(1<<x)];
				vis[x][p&((2<<x)-1)]=1,anss+=(ans[x][p&((2<<x)-1)]=ansa);
			}
		}
	}
	printf("%lld",anss);
	return 0;
}