LOJ 6281 数列分块入门 5

简化版题意

给出一个长为n的数列，以及n个操作，操作涉及区间开方（每个数都向下取整），区间求和，保证所有数都为有符号32位正整数。

N<=50000

Solution

首先我们先思考：

一个有符号32位正整数最多只能被开方几次就会得到相同的值？

\(Example\)：\(2147483647=2^{31}-1\)

最多5次（由于是向下取整）

所以，我们将数列中的每一个数，都开方5次，复杂度为\(O(5n)\)

然后我们再来考虑如何分块

对于每一个块，我们可以打一个标记\(tag[i]\)

表示第\(i\)块是否全为\(1\)

然后我们就可以进行分块处理啦

对于区间\([l,r]\)

对于区间求和，暴力分块统计即可

对于操作二

对于不完整的块，暴力开方即可

对于完整的块，先利用\(tag[i]\)判断是否需要开方，然后继续暴力

完结撒花！

贴代码

\\还是很可读的，就不给注释了

#include<bits/stdc++.h>

using namespace std;

const int siz=1e6+10;

int num[siz];

int tag[siz],s[siz],b[siz];

int n,len;

int sum(int l,int r)

{

	int ans=0;

	if(b[l]==b[r])

	{

		for(int i=l;i<=r;++i)

			ans+=num[i];

		return ans;

	}

	for(int i=l;b[i]==b[l];++i) ans+=num[i];

	for(int i=r;b[i]==b[r];--i) ans+=num[i];

	for(int i=b[l]+1;i<=b[r]-1;++i) ans+=s[i];

	return ans;

}

void add(int l,int r)

{

	if(b[l]==b[r])

	{

		if(tag[b[l]]) return ;

		for(int i=l;i<=r;++i)

			s[b[i]]-=num[i],num[i]=sqrt(num[i]),s[b[i]]+=num[i];

		return ;

	}

	if(!tag[b[l]])

	for(int i=l;b[i]==b[l];++i)

		s[b[i]]-=num[i],num[i]=sqrt(num[i]),s[b[i]]+=num[i];

	if(!tag[b[r]])

	for(int i=r;b[i]==b[r];--i)

		s[b[i]]-=num[i],num[i]=sqrt(num[i]),s[b[i]]+=num[i];

	for(int i=b[l]+1;i<=b[r]-1;++i)

	{

		if(tag[i]) continue;

		tag[i]=1;

		for(int j=len*(i-1)+1;b[j]==i;++j)

		{

			s[i]-=num[j],num[j]=sqrt(num[j]),s[i]+=num[j];

			if(num[j]>1) tag[i]=0;

		}

	}

}

int main()

{

	scanf("%d",&n);

	len=sqrt(n);

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

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

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

	{

		b[i]=(i-1)/len+1;

		s[b[i]]+=num[i];

	}

	int opt,l,r,c;

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

	{

		scanf("%d%d%d%d",&opt,&l,&r,&c);

		if(opt) printf("%d\n",sum(l,r));

		else add(l,r);

	}

	return 0;

}

巴特西

LOJ 6281 数列分块入门 5

简化版题意

Solution

最新文章

热门文章