洛谷P4145:https://www.luogu.org/problemnew/show/P4145
思路
这道题的重点在于sqrt(1)=1 一个限制条件
与正常线段树不同的是区间修改为开方
那么我们用一个数组记录每个区间的最大值 只有当这个区间的最大值大于1时才需要开方
因此 当我们更新到叶子节点时把每个区间的最大值和sum值开方即可
注意题目中说l可能大于r 要交换
代码
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define maxn 100010
ll sum[maxn<<],Max[maxn<<],a[maxn];
ll n,m;
void build(ll l,ll r,ll k)
{
if(l==r)
{
sum[k]=a[l];
Max[k]=sum[k];//叶子节点
return;
}
ll mid=(l+r)>>;
build(l,mid,k<<);
build(mid+,r,k<<|);
sum[k]=sum[k<<]+sum[k<<|];
Max[k]=max(Max[k<<],Max[k<<|]);//更新上层的值
return;
}
ll query(ll x,ll y,ll l,ll r,ll k)//常规询问
{
if(x<=l&&r<=y) return sum[k];
ll res=;
ll mid=(l+r)>>;
if(x<=mid) res+=query(x,y,l,mid,k<<);
if(y>mid) res+=query(x,y,mid+,r,k<<|);
return res;
}
void update(ll x,ll y,ll l,ll r,ll k)
{
if(l==r)//叶子节点时
{
sum[k]=sqrt(sum[k]);
Max[k]=sqrt(Max[k]);
return;
}
ll mid=(l+r)>>;
if(x<=mid&&Max[k<<]>) update(x,y,l,mid,k<<);//满足最大值大于1
if(y>mid&&Max[k<<|]>) update(x,y,mid+,r,k<<|);
sum[k]=sum[k<<]+sum[k<<|];//更新上层的值
Max[k]=max(Max[k<<],Max[k<<|]);
}
int main()
{
cin>>n;
for(ll i=;i<=n;i++) cin>>a[i];
build(,n,);
cin>>m;
for(ll i=;i<=m;i++)
{
ll k,l,r;
cin>>k>>l>>r;
if(l>r)//交换
{
int temp;
temp=l;
l=r;
r=temp;
}
if(k==)
{
update(l,r,,n,);
}
if(k==)
{
cout<<query(l,r,,n,)<<endl;
}
}
}
【题解】洛谷P4145 花神游历各国(线段树)的更多相关文章
-
BZOJ 3211: 花神游历各国( 线段树 )
线段树...区间开方...明显是要处理到叶节点的 之前在CF做过道区间取模...差不多, 只有开方, 那么每个数开方次数也是有限的(0,1时就会停止), 最大的数10^9开方10+次也就不会动了.那么 ...
-
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
-
bzoj3211 花神游历各国 线段树,势能分析
[bzoj3211]花神游历各国 2014年3月17日2,7230 Description Input Output 每次x=1时,每行一个整数,表示这次旅行的开心度 Sample Input ...
-
bzoj3211: 花神游历各国(线段树) 同codevs2492
3211: 花神游历各国 Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 3628 Solved: 1326[Submit][Status][Discu ...
-
BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
-
bzoj3211花神游历各国 线段树
3211: 花神游历各国 Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 4252 Solved: 1547[Submit][Status][Discu ...
-
BZOJ3211:花神游历各国(线段树)
Description Input Output 每次x=1时,每行一个整数,表示这次旅行的开心度 Sample Input 4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 ...
-
BZOJ3211花神游历各国-线段树&;树状数组-(HDU4027同类型)
(有任何问题欢迎留言或私聊 && 欢迎交流讨论哦 题意:BZOJ HDU 原题目描述在最下面. 两种操作,1:把区间的数字开方一次,2:区间求和. 思路: 线段树: 显然不能暴力 ...
-
day1 晚上 P4145 上帝造题的七分钟2 / 花神游历各国 线段树
#include<iostream> #include<cstdio> #include<cmath> using namespace std; ; struct ...
随机推荐
- 《Head First Servlet JSP》学习笔记
-
requirejs 优化压缩
1 配置node环境 2 配置built.js文档 3 执行命令node r.js -o built.js 文件目录: <!DOCTYPE HTML> <html lang=&quo ...
-
StringBuilder是不是线程安全的?
测试条件: 开启2个并行执行任务,往同一个StringBuilder对象写入值 测试代码: ; static StringBuilder sbIsThreadSafe = new StringBuil ...
-
php代理
有些网上接口请求需要用代理 php代码 <?php header('Access-Control-Allow-Origin:*'); $url=$_POST['urlString']; $res ...
-
关于ckeditor5设置高度
在管理端模板AdminBSBMaterialDesign-master里发现一个比百度编辑器看起来更高大上的编辑器:ckeditor.模板中使用的是版本4,自己在官网上下载了最新版本.在之前的版本,使 ...
-
ONOS架构-概览
这个是阅读https://wiki.onosproject.org/display/ONOS/Architecture+Guide是顺便翻译的,目前断断续续在阅读,今天先贴一部分 概览 基于osgi, ...
-
FZU 2150 Fire Game(点火游戏)
FZU 2150 Fire Game(点火游戏) Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description - 题目描述 ...
-
亚马逊aws 一个实例双网卡-两个弹性ip设置
一个实例默认只有1个网络接口: 步骤一.创建一个新的网络接口,附加到实例. 步骤二.手动添加路由 增加两个路由表,为后续的双网关做点小准备: vim /etc/iproute2/rt_tables 添 ...
-
ES配置文件中文版
##################### Elasticsearch Configuration Example ##################### # This file contains ...
-
FLume监控文件夹,将数据发送给Kafka以及HDFS的配置文件详解
详细配置文件flume-conf.properties如下: ############################################ # producer config ###### ...