3 条题解
-
3
提供一个 的做法
Solution
首先一个重要的性质: $\text{对于 }x=0,1,2\dots,x \text{ 在二进制第 }k\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{ 的个数}$ ,时间复杂度为对于每次操作 ,用偏移量 累加 ,每次询问时,通过 数组 统计。
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
- 上传者