Codeforces 920F 线段树

最新推荐文章于 2022-04-01 22:58:06 发布

animalcoder

最新推荐文章于 2022-04-01 22:58:06 发布

阅读量322

点赞数

分类专栏： ACM--线段树文章标签： Codeforces 线段树简单数论

本文链接：https://blog.csdn.net/animalcoder/article/details/79371430

版权

ACM--线段树专栏收录该内容

14 篇文章

订阅专栏

题意：

查询：区间查询【l,r】数列的和

修改：区间修改【l,r】ai->d(ai)

d(x)是x的因子个数比如d(6)=4 (1,2,3,6四个)

思路：

查询：维护区间数列和sum，满足区间合并

修改：尝试暴力修改到叶子+剪枝

发现x多次d(x)是会收敛的d（2）=2，d（1）=1

所以当区间内的值都是<=2的话我们就不用向下继续更新了

那怎么知道区间的值都<=2呢。。

维护区间最大值即可

d(x)预处理一下，对每个因子i更新d(j) j=ki,k>=1

思维难度：0.6，实现难度0.7

跟BZOJ3038类似：那题修改是ai->向下取整sqrt(ai)

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define ll long long
int d[1000005]; 

struct stree{
	ll sum;
	ll mx;
}sts[300002*4];
ll a[1000005];
void pushup(int root)
{
	sts[root].sum=sts[root<<1].sum+sts[root<<1|1].sum;
	sts[root].mx=max(sts[root<<1].mx,sts[root<<1|1].mx);
}
void init()
{
	for(int i=1;i<=1000000;i++)
		for(int j=i;j<=1000000;j+=i)
			d[j]++;
}
void build(int l,int r,int root)
{
	if(l==r)
	{
		sts[root].sum=sts[root].mx=a[l];
	}
	else
	{
		int mid=(l+r)>>1;
		build(l,mid,root<<1);
		build(mid+1,r,root<<1|1);
		pushup(root);
	}
}

void update(int nowl,int nowr,int ul,int ur,int root)
{
	if(nowl==nowr)
	{
		sts[root].mx=sts[root].sum=d[sts[root].sum];
		return ;
	}
	if(ul<=nowl&&ur>=nowr&&sts[root].mx<=2)return ;
	int mid=(nowl+nowr)>>1;
	if(ul<=mid)update(nowl,mid,ul,ur,root<<1);
	if(ur>mid)update(mid+1,nowr,ul,ur,root<<1|1);
	pushup(root);
}

ll query(int nowl,int nowr,int ql,int qr,int root)
{
	if(ql<=nowl&&qr>=nowr)
	{
		return sts[root].sum;
	}
	else
	{
		int mid=(nowl+nowr)>>1;
		ll ans=0;
		if(ql<=mid)ans+=query(nowl,mid,ql,qr,root<<1);
		if(qr>mid)ans+=query(mid+1,nowr,ql,qr,root<<1|1);
		return ans;
	}
}
void op();
int main()
{
	init();
//	for(int i=1;i<=10;i++)
//		printf("%d %d\n",i,d[i]);
	int n,m;int t,l,r;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%I64d",&a[i]);
	build(1,n,1);
//	op();
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&t,&l,&r);
		if(t==1)
		{
			update(1,n,l,r,1);
		//	op();
		}
		else
		{
			printf("%I64d\n",query(1,n,l,r,1));
		}
	}
}

void sp(int t)
{
	for(int i=1;i<=t;i++)
	printf(" ");
}
void op()
{
	int pow2[10]={1,2,4,8,16,32};int n=16;
	printf("\n///\n");
	for(int i=1; i<=31; i++)
	{
		if(i==pow2[0])sp(15);
		if(i==pow2[1])sp(7);
		if(i==pow2[2])sp(3);
		if(i==pow2[3])sp(1);
		if(i>pow2[1]&&i<pow2[2])sp(15);
		if(i>pow2[2]&&i<pow2[3])sp(7);
		if(i>pow2[3]&&i<pow2[4])sp(3);
		if(i>pow2[4]&&i<pow2[5])sp(1);
		printf("%d",sts[i].mx);
		if((i==pow2[1]-1)||(i==pow2[2]-1)||(i==pow2[3]-1)||(i==pow2[4]-1))
			printf("\n");
	}
	printf("\n\n///\n");
}