Codeforces 920F 线段树

题意:

查询:区间查询【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");
}

关于 Codeforces Round 605 的 Problem F 题目及其解决方案,目前并未提供具体的内容作为参考依据。然而,可以基于常见的竞赛编程策略以及题目可能涉及的主题来推测其解决方法。 通常情况下,在处理复杂算法问题时,尤其是像 Codeforces 这样的平台上的高难度题目(如Problem F),可能会涉及到高级数据结构或者优化后的动态规划技术。以下是针对此类问题的一些通用技巧: ### 可能使用的算法和技术 #### 1. **高级数据结构** 如果问题是围绕高效查询和更新展开,则可能需要用到诸如线段树(Segment Tree)[^3] 或者平衡二叉搜索树(Fenwick Tree/Binary Indexed Tree)[^4]这样的高级数据结构。 ```cpp // 示例:构建简单线段树用于区间求和操作 struct SegmentTree { int size; vector<long long> sums; void init(int n){ size = 1; while(size <n)size *=2; sums.assign(2*size,0LL); } void build(vector<int>& a,int x ,int lx ,int rx ){ if(rx-lx==1){ if(lx<(int)a.size())sums[x]=a[lx]; return ; } int m=lx+(rx-lx)/2; build(a,2*x+1,lx,m); build(a,2*x+2,m,rx); sums[x]=sums[2*x+1]+sums[2*x+2]; } void set_val(int i ,int v ,int x ,int lx ,int rx ){ if(rx-lx==1){ sums[x]=v; return ; } int m=lx+(rx-lx)/2; if(i<m)set_val(i,v,2*x+1,lx,m); else set_val(i,v,2*x+2,m,rx); sums[x]=sums[2*x+1]+sums[2*x+2]; } long long sum(int l ,int r ,int x ,int lx ,int rx ){ if(l>=rx ||r<=lx)return 0; if(lx >=l &&rx <=r )return sums[x]; int m=lx+(rx-lx)/2; long long s1=sum(l,r,2*x+1,lx,m); long long s2=sum(l,r,2*x+2,m,rx); return s1+s2; } }; ``` #### 2. **动态规划(DP)** 对于某些组合类或路径寻找的问题,动态规划可能是最有效的手段之一。通过定义状态转移方程并利用记忆化存储中间结果,能够显著降低时间复杂度[^5]。 #### 3. **图论模型转换** 部分难题可以通过建模成特定类型的图形来进行解答,比如最小生成树(MST),最大流(Max Flow)等问题都属于这一范畴。这类问题往往需要借助成熟的库函数或是自己实现相应的算法逻辑[^6]。 由于缺乏具体的题目描述信息,上述仅为假设性的分析方向。为了获得更精确的指导建议,请提供更多有关该道题目的细节说明。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值