题目描述
输入
输出
样例输入
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
",ans);
}
}
return 0;
}启发
当十进制与二进制碰撞在一起的时候，尝试把二进制转化为十进制，尤其涉及加减乘除之类的运算时。