3 条题解

  • 3
    @ 2026-10-23 10:54:05

    提供一个 O(nlogV)O(nlogV) 的做法

    Solution

    首先一个重要的性质: $\text{对于 }x=0,1,2\dots,x \text{ 在二进制第 }k\text{ 位上的数变化呈周期性。}$ 如:

    k=1:0,0,1,1,0,0,1,1,0,0,1,1…k=1:0,0,1,1,0,0,1,1,0,0,1,1\dots

    k=2:0,0,0,0,1,1,1,1,0,0,0,0…k=2:0,0,0,0,1,1,1,1,0,0,0,0\dots

    k=3:0,0,0,0,0,0,0,0,1,1,1,1,1…k=3:0,0,0,0,0,0,0,0,1,1,1,1,1\dots

    所以我们可以预处理出 对于每个 ai,(ai+x)&2j 的值 \text{对于每个 }a_i,(a_i+x)\&2^j\text{ 的值 }

    for(int i=1;i<=n;i++){
    		cin>>a[i];
    		for(int j=0;j<L;j++){
    			int x=a[i]%(1<<j),t=a[i]/(1<<j);
    			if(t&1){
    				c[(1<<j)-x][j]++;
    				c[1<<j][j]--;
    			}
    			else{
    				c[0][j]++;
    				c[(1<<j)-x][j]--;
    			}
    		}
    	}
    	for(int j=0;j<L;j++)
    		for(int i=1;i<(1<<j);i++)
    			c[i][j]+=c[i-1][j];
    

    其中c[x][j]表示 $\text{满足 }(a_i+x)\&2^j=x\&2^j\text{ 的 }a_i\text{ 的个数}$ ,时间复杂度为 O(nlogV)O(nlogV)

    对于每次操作 AA ,用偏移量 delatdelat 累加 xx ,每次询问时,通过 cc 数组 O(1)O(1) 统计。

    Code

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10,L=20,mod=1<<16;
    int n,m;
    long long ans;
    int a[N],c[1<<L][L];
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		for(int j=0;j<L;j++){
    			int x=a[i]%(1<<j),t=a[i]/(1<<j);
    			if(t&1){
    				c[(1<<j)-x][j]++;
    				c[1<<j][j]--;
    			}
    			else{
    				c[0][j]++;
    				c[(1<<j)-x][j]--;
    			}
    		}
    	}
    	for(int j=0;j<L;j++)
    		for(int i=1;i<(1<<j);i++)
    			c[i][j]+=c[i-1][j];
    	int x,delta=0;
    	string op;
    	while(m--){
    		cin>>op>>x;
    		if(op[0]=='A')
    			delta=(delta+x)%mod;
    		else{
    			int t=delta/(1<<x);
    			int s=delta%(1<<x);
    			if(t&1) ans+=c[s][x];
    			else ans+=n-c[s][x];
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    

    信息

    ID
    937
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    147
    已通过
    8
    上传者