3 条题解

  • 0
    @ 2026-10-24 9:59:39

    SOLUTION

    显然直接放到值域上考虑,令 V=65536V=65536。

    题目所述其实就是第 ii 位是 11 的数的数量。

    观察 i=0i=0,得这样的数有:

    x∈1,3,5,7,9,11,13,15,...x \in {1,3,5,7,9,11,13,15,...}

    观察 i=1i=1:

    x∈2,3,6,7,10,11,14,15,18,19,22,23,...x \in {2,3,6,7,10,11,14,15,18,19,22,23,...}

    更一般地,对于 i=ti=t:

    x∈[2t+1k+2t,2t+1k+2t+1−1],k∈Nx \in [2^{t+1}k+2^t,2^{t+1}k+2^{t+1}-1],k \in \N

    可以发现,xx 所在的是一段一段的前缀和,考虑预处理出 si,j,fi,js_{i,j},f_{i,j},其中 si,js_{i,j} 代表要求的是第 jj 位,以 ii 为结尾的 xx 的数量,fi,jf_{i,j} 是以 ii 为开头的,其他同理。

    在修改操作时维护偏移量 deltadelta,查询时令 V′V' 为 VV 偏移到的位置,于是答案就是 sV′,i+fV′+1,is_{V',i}+f_{V'+1,i}。

    总复杂度为预处理与查询 O(M+Vlog⁡V)O(M+V \log V)。

    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
    上传者