题目

分析

首先每个数对\(2^i\)取模。也就是把每个数的第i位以后删去。

把它们放进树状数组里面。

那么当查询操作，

答案就位于区间\([2^i-x,2^{i-1}-1-x]\)中，直接查询就可以了。

细节很多，注意处理。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long mo=1000000007;

const long long N=100005;

using namespace std;

long long tree[N*11][25];

long long a[N],n,q,mi[25];

int twobird(int x)

{

	return x&(-x);

}

int insert(long long k,int j)

{

	k++;

	while(k<=mi[20])

	{

		tree[k][j]+=1;

		k+=twobird(k);

	}

}

int delete1(long long k,int j)

{

	k++;

	while(k<=mi[20])

	{

		tree[k][j]-=1;

		k+=twobird(k);

	}

}

int find(long long k,int j)

{

	k++;

	int sum=0;

	while(k>=1)

	{

		sum+=tree[k][j];

		k-=twobird(k);

	}

	return sum;

}

int main()

{

	mi[0]=1;

	for(int i=1;i<=22;i++) mi[i]=mi[i-1]*2;

	scanf("%lld%lld",&n,&q);

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

	{

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

		for(int j=20;j>=0;j--) insert(a[i]%mi[j],j);

	}

	for(int i=1;i<=q;i++)

	{

		long long opt,x,y;

		scanf("%lld%lld%lld",&opt,&x,&y);

		if(opt==1)

		{

			for(int j=20;j>=0;j--) delete1(a[x]%mi[j],j);

			a[x]=y;

			for(int j=20;j>=0;j--) insert(a[x]%mi[j],j);

		}

		else

		{

			long long ans=0;

			for(int j=20;j>=0;j--)

			{

				if(y-mi[j]>=0)

				{

					long long x1=((mi[j]-x)%mi[j+1]+mi[j+1])%mi[j+1],x2=((mi[j+1]-x-1)%mi[j+1]+mi[j+1])%mi[j+1];

					if(x1<=x2)

						ans+=(find(x2,j+1)-find(x1-1,j+1))*mi[j];

					else

					{

						ans+=(find(mi[j+1]-1,j+1)-find(x1-1,j+1)+find(x2,j+1))*mi[j];

					}

					y-=mi[j];

				}

			}

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

		}

	}

}

巴特西

【NOIP2016提高A组模拟8.17】(雅礼联考day1)Binary

题目

分析

最新文章

热门文章