【JZ雅礼联考】Binary 题解

题目大意

  给定一个长度为 $n$ 的整数数列 $a$ 和 $q$ 次操作：
  修改操作：形如 1 x y，表示将 $a_x$ 的值修改为 $y$；
  询问操作：形如 2 x y，表示询问$\sum_1^n(a_i+x)~and~y$的值。
  $n,q \le 10^5$
  $0 \le a_i,x,y \le 2^{20}$

【40%】n,q<=5000

  题目怎么说怎么做。

【另20%】所有询问的x=0

  二进制总共只有20位，直接记录每一位为1的有多少个数，假设记为cnt[i]查询时，y的第i个二进制位为1，就答案加上$2^i*cnt[i]$。

【100%】n,q<=10^5

  我们还是对于每个二进制位单独考虑，且y这一位为1才考虑。
  不考虑+x时，我们还可以弄一棵值域线段树，那么cnt[i]所包含的数就是这样的：比i高的位任意，i位以内满足在 $[2^{i-1},2^i-1]$ 这个区间内。可以发现我们查询的区间对于整个值域来说并不连续，而是一段一段的，因此我们对每个二进制位都开一棵值域线段树，第i位的线段树存储的数则由 $a_i$ 变为 $a_i \bmod 2^i$。这样我们操作第i位时，直接在第i位的线段树中查询$[2^{i-1},2^i-1]$内的数有多少个，就行了。
  接下来考虑+x。这个实际上是对查询区间的位移，比如当前查询区间$[2^{i-1},2^i-1]$，那么就变成$[2^{i-1}-x,2^i-1-x]$。要注意这里的x是$mod~2^i$的。唯一的问题就是区间左端点可能为负。这好办，先把0到右端点的正常操作，假设左端点变成了$-z$，那我们再查询$[2^i-z,2^i-1]$就行了。这里相当于是退位一样的东西。

代码

//我把线段树换成树状数组，这样常数小代码短

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=(1e5)+5, MX=20, maxc=(1<<20)+5;

int n,a[maxn],er[MX+5];

int c[MX+2][maxc];
int lowbit(int x) {return x&(-x);}
void xg(int ty,int x,int z)
{
	if (x==0) {c[ty][0]+=z; return;}
	for(; x<er[ty]; x+=lowbit(x)) c[ty][x]+=z;
}
int get(int ty,int x)
{
	if (x<0) return 0;
	int re=0;
	for(; x; x-=lowbit(x)) re+=c[ty][x];
	return re+c[ty][0];
}

int q;
int main()
{
	fo(i,0,MX) er[i]=1<<i;
	
	scanf("%d %d",&n,&q);
	fo(i,1,n)
	{
		scanf("%d",&a[i]);
		fo(j,1,20) xg(j,a[i]%er[j],1);
	}
	
	while (q--)
	{
		int ty,x,y;
		scanf("%d %d %d",&ty,&x,&y);
		if (ty==1)
		{
			fo(i,1,20) xg(i,a[x]%er[i],-1);
			fo(i,1,20) xg(i,y%er[i],1);
			a[x]=y;
		} else
		{
			LL ans=0;
			fo(i,1,MX) if (y&er[i-1])
			{
				int xx=x%er[i], st=er[i-1]-xx, en=er[i]-1-xx;
				if (st<0)
				{
					ans+=(LL)er[i-1]*get(i,en);
					if (i>1) ans+=(LL)er[i-1]*(get(i,er[i]-1)-get(i,er[i]+st-1));
				} else
				{
					ans+=(LL)er[i-1]*(get(i,en)-get(i,st-1));
				}
			}
			
			printf("%lld\n",ans);
		}
	}
}