3 条题解
-
0
SOLUTION
显然直接放到值域上考虑,令 。
题目所述其实就是第 位是 的数的数量。
观察 ,得这样的数有:
观察 :
更一般地,对于 :
可以发现, 所在的是一段一段的前缀和,考虑预处理出 ,其中 代表要求的是第 位,以 为结尾的 的数量, 是以 为开头的,其他同理。
在修改操作时维护偏移量 ,查询时令 为 偏移到的位置,于是答案就是 。
总复杂度为预处理与查询 。
CODE
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,m; int N=65536; int a[101000],s[101000][17],f[101000][17]; int del=0; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ int x; cin>>x; a[x+1]++; } for(int i=1;i<=N;i++){ s[i][0]=s[i-1][0]+a[i]; for(int j=1;j<=16;j++){ s[i][j]=s[max(0ll,i-(1<<j))][j]+s[i][0]-s[max(0ll,i-(1<<(j-1)))][0]; } } for(int i=N;i>=1;i--){ for(int j=1;j<=16;j++){ f[i][j]=f[min(N+1,i+(1<<j))][j]+s[min(N+1,i+(1<<j))-1][0]-s[min(N+1,i+(1<<(j-1)))-1][0]; } } int ans=0; while(m--){ char op; int x; cin>>op>>x; if(op=='A') del=(del+x)%N; else{ if(x>=16) continue; int t=(N-1-del+N)%N+1; ans+=s[t][x+1]+f[t+1][x+1]; } } cout<<ans<<'\n'; return 0; }
信息
- ID
- 937
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 147
- 已通过
- 8
- 上传者