自动搬运

查看原文

来自洛谷，原作者为

	一念之间、、 Have already AFOed.

搬运于2025-08-24 22:14:21，当前版本为作者最后更新于2021-07-31 19:26:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意十分明了，

发现修改和询问是对于整个序列进行的处理，且询问只有 $16$ 种，发现在询问 $i$ 的时候比 $i$ 高的位都没有用，

所以考虑对每个 $i$ 开一个桶，记录小于等于 $2^i$ 的所有数是多少，对于 $i$ 询问会发现 $i$ 位为 $1$ 的一定是一段连续的区间，所以同时记录 $dlt$ ，加入一个偏移量，前缀和询问即可，

时间复杂度 $O(16\times2^{16}+n+m)$ 空间复杂度 $O(16\times2^{16})$

其实还有另外一个更好想到，更暴力的思路，将前 $8$ 位与后 $8$ 位分别进行处理，后 $8$ 位可以进行枚举，前 $8$ 位按照区间连续段前缀和询问即可

时间复杂度 $O(2^{8}\times m)$ 空间复杂度 $O(2^{16})$

这里给出第二种代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int n,m,t[65537],s[257],dlt=0;
int get(int l,int r)
{
	if(l<0)l+=65536*20;
	if(r<0)r+=65536*20;
	l%=65536,r%=65536;
	if(l<=r)return t[r]-((l!=0)?t[l-1]:0);
	return get(0,r)+get(l,65535);
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		int o=read();
		t[o]++;s[o%256]++;
	}
	for(int i=1;i<65536;i++)t[i]+=t[i-1];
	while(m--)
	{
		char c;
		while((c=getchar())!='C'&&c!='Q');
		if(c=='C')dlt+=read(),dlt%=65536;
		else 
		{
			int a=read(),ans=0;
			if(a<=7)
			{
				for(int i=0;i<256;i++)
					if(i>>a&1)ans+=s[(i-dlt+256*1000)%256];
			}
			else 
			{
				for(int i=0;i<256;i++)
					if(i>>(a-8)&1)ans+=get(i*256-dlt,(i+1)*256-1-dlt);
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}