【CQOI2008】位统计

一念之间、、 · 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;
}