题目描述

输入

输出

样例输入

6 6

8 9 1 13 9 3

1 4 5

2 6 9

1 3 7

2 7 7

1 6 1

2 11 13

样例输出

45

19

21

数据范围

解法

40%暴力即可；

60%分段暴力，对于20%的数据，由于没有x，所以y二进制下，每有一个1，就计算对应位置有多少1就可以了。

100%基于60%的想法，如果y&(1 shl (i-1))有值（y在二进制下的第i位是1），那么就相当于有多少个a在mod(1 shl i)意义下，在[1 shl (i-1)..(1 shl i)-1]这个区间内。

所以把a依次mod(1 shl i)并在第i个桶状树状数组对应数值位置+1。

修改的时候，把原来的a在树状数组上做出的贡献剔除，再加入新的贡献即可。

询问的时候，正如上述所做，当x>0的时候，那么相当于把[1 shl (i-1)..(1 shl i)-1]这个区间整体向做移动成[1 shl (i-1)-x..(1 shl i)-1-x]，在计算区间内有多少个数即可。

棘手的是，区间有时候会囊括到负编号，左边界可能为负，右边界也有可能为负；这时候把负边界mod以(1 shl i)，在计算答案即可。感性理解：假定负边界值为z，那么x>z，才会导致z-x为负数，将其mod以(1 shl i)得到z’后，z’再加回x，会导致最高位进位，然后在(1 shl i)意义下，最高位进位变为0，x把z’变为0之后，x还能把0加到z。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="aP3.in";

const char* fout="aP3.out";

const int inf=0x7fffffff;

const int maxn=100007,maxk=21;

int n,m,i,j,k,o,mo,tmp,tmd,t1,t2,t3;

ll ans;

int a[maxn];

struct ctree{

    int data[1<<maxk],limit;

    void change(int v,int v1){

        v+=2;

        for (;v<=limit;v+=v&-v) data[v]+=v1;

    }

    int getsum(int v){

        int k=0;

        v+=2;

        for (;v;v-=v&-v) k+=data[v];

        return k;

    }

}c[maxk];

void count(int a,int b){

    for (int i=1;i<maxk;i++) c[i].limit=1<<(i+1),c[i].change(a%(1<<i),b);

}

int main(){

    scanf("%d%d",&n,&m);

    for (i=1;i<=n;i++) {

        scanf("%d",&a[i]);

        count(a[i],1);

    }

    for (i=1;i<=n;i++){

        scanf("%d",&j);

        if (j==1){

            scanf("%d%d",&j,&k);

            count(a[j],-1);

            a[j]=k;

            count(a[j],1);

        }else{

            scanf("%d%d",&j,&k);

            ans=0;

            for (o=1;o<maxk;o++)

                if (k&(1<<(o-1))){

                    tmp=(1<<o)-1-j;

                    tmp=(tmp%(1<<o)+(1<<o))%(1<<o);

                    tmd=(1<<(o-1))-j;

                    tmd=(tmd%(1<<o)+(1<<o))%(1<<o);

                    if (tmp>=tmd) ans+=(ll)(c[o].getsum(tmp)-c[o].getsum(tmd-1))*(1<<(o-1));

                    else{

                        t1=c[o].getsum(tmp);

                        t2=c[o].getsum((1<<o)-1);

                        t3=c[o].getsum(tmd-1);

                        ans+=(ll)(t1+t2-t3)*(1<<(o-1));

                    }

                }

            printf("%lld\n",ans);

        }

    }

    return 0;

}

启发

当十进制与二进制碰撞在一起的时候，尝试把二进制转化为十进制，尤其涉及加减乘除之类的运算时。