「BJWC2008」序列

题意：一个长度为 $n$ 的序列 $a _{i}(a _{i}\in [0,2 ^{16}-1])$，进行以下 $2$ 种共 $m$ 个操作：

• A x，其中满足 $x\ge 0$，将所有 $a _{i}$ 加上 $x$，对 $2 ^{16}$ 取模；
• Q i，询问序列中有多少个数第 $i+1$ 位为 $1$，即 $\text{card}\{k|a _{k}~\text{and}~ 2 ^{i}>0 ,1\le k\le n,k\in \mathbb{Z}\}$。

求出所有询问的和。

数据范围与约定：

对于 $30\%$ 的数据满足 $1\le n\le 100,1\le m\le 1000$；

对于 $100\%$ 的数据满足 $1\le n,m\le 10 ^{5}$。

解析：一道很妙的数据结构题。

题目让我们支持两个操作，全局加和询问，由于是全局加，所以对于所有的加操作我们可以用一个变量 $p$ 记录下来已经加了多少。

对于每个 $a _{i}$，如果 $(a _{i}+p)~\text{and}~2 ^{i}=1$ 的话说明 $a _{i}+p$ 二进制展开后从第 $i$ 位开始的后缀在 $2 ^{i}$ 到 $2 ^{i+1}-1$ 之间，即 $100\cdots 000\sim 1111\cdots 111$。即 $a _{i}$ 在 $2 ^{i}-p\sim 2 ^{i+1}-1-p$ 之间(在模 $2 ^{i+1}$ 意义下，即后 $i$ 位)。所以我们对于每个长度的后缀分别开一个权值线段树查询即可。时间复杂度为 $O((n+m)\log v)$，其中 $v$ 是值域，满足 $\max v=2 ^{16}$。

另一个查询某一个区间内有多少个数的方法是用桶把所有数存下来，然后用前缀和 $sum _{i,j}$ 来查询后缀长度为 $i$ 位从 $0\sim j$ 有多少个数，查询后 $x$ 位下 $[l,r]$ 之间有多少数即 $sum _{x,r}-sum _{x,l-1}$。时间复杂度是 $O(n\log v +m)$，不过常数要比线段树小得多。

/*
 * @Author: clorf 
 * @Date: 2020-12-01 17:53:56 
 * @Last Modified by: clorf
 * @Last Modified time: 2020-12-01 20:28:22
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<cctype>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define INF 2e9
using namespace std;
const int maxn=1<<18;
const double Pi=acos(-1.0);
const double eps=1e-7;
//1.数组开小
//2.没用long long/爆了类型存储范围
//3.写之前式子没推清楚
//4.变量写错(想当然typo/没想清楚含义)
//5.写之前没想清楚复杂度
//6.常量数字与long long连用时要加ll！！！
//7.考虑无解和多解的情况
//8.两个int连成爆long long的一定要加1ll！！！！
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
int n,m,p;
int sum[17][maxn+5];
long long ans;
inline void pushup(int type,int rt)
{
    sum[type][rt]=sum[type][rt<<1]+sum[type][rt<<1|1];
}
void update(int type,int x,int val,int l,int r,int rt)
{
    if(l==r)
    {
        sum[type][rt]+=val;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        update(type,x,val,lson);
    else
        update(type,x,val,rson);
    pushup(type,rt);
}
inline int query(int type,int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
        return sum[type][rt];
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)
        ans+=query(type,L,R,lson);
    if(R>mid)
        ans+=query(type,L,R,rson);
    return ans;
}
char s[2];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        int num=0;
        for(int j=0;j<16;j++)
        {
            num+=(x&(1<<j));
            update(j,num,1,0,(1<<(j+1))-1,1);
        }
    }
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            int x;
            scanf("%d",&x);
            p+=x;
        }
        else
        {
            int x;
            scanf("%d",&x);
            if(x>=16)
            {
                printf("0");
                continue;
            }
            int l=1<<x;
            int r=(l<<1)-1;
            int mod=r+1;
            l=(l-p%mod+mod)%mod;
            r=(r-p%mod+mod)%mod;
            if(l<=r)
                ans+=query(x,l,r,0,(1<<(x+1))-1,1);
            else
                ans+=query(x,l,(1<<(x+1))-1,0,(1<<(x+1))-1,1)+query(x,0,r,0,(1<<(x+1))-1,1);
        }
    }
    printf("%lld",ans);
    return 0;
}