题解 P4641 【[BJWC2008]序列】

123456zmy · 2020-09-04 19:34:24 · 题解

题意：
给你一个序列，支持全局加及查询二进制某位为 1 的数的个数，序列中的数对 65536 取模。

设序列中的数的值域为 v。

注意到操作都是全局的，所以序列中的数可以开桶来存，全局加也可以用标记解决。

对于查询，需要计入答案的数的区间是 [k\cdot2^{i+1}+2^i,(k+1)\cdot2^{i+1})，暴力 O(mv)。加个指令集就可以过了，代码。

通过观察发现其答案只与加上的数的和的后 i 位有关，用前缀和及记忆化优化后可以通过此题。可以卡到最优解。

AC代码：（O(n+v\log v),191ms）

#include<bits/stdc++.h>
int n,m,a2;
char c;
unsigned short p,x;
int sum[131088],cnt[131088],ans[17][65537];
bool vis[17][65537];
int main()
{
    register long long anss=0;
    register unsigned short p=0;
    scanf("%d%d",&n,&m); 
    for(int i=0;i<n;i++)scanf("%d",&a2),++cnt[a2],++cnt[a2+65536];
    sum[0]=cnt[0];
    for(int i=1;i<131088;i++)sum[i]=sum[i-1]+cnt[i];
    while(m--)
    {
        scanf("%s%d",&c,&x);
        if(c=='A')p+=x;
        else
        {
            if(vis[x][p&((2<<x)-1)])anss+=ans[x][p&((2<<x)-1)];
            else
            {
                register int ansa=0;
                for(register int i=(2<<x)-1;i<65536;i+=2<<x)ansa+=sum[65536-p+i]-sum[65536-p+i-(1<<x)];
                vis[x][p&((2<<x)-1)]=1,anss+=(ans[x][p&((2<<x)-1)]=ansa);
            }
        }
    }
    printf("%lld",anss);
    return 0;
}