【题解】洛谷P4145 花神游历各国(线段树)

时间:2022-02-08 03:51:29

洛谷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 花神游历各国(线段树)的更多相关文章

  1. BZOJ 3211&colon; 花神游历各国&lpar; 线段树 &rpar;

    线段树...区间开方...明显是要处理到叶节点的 之前在CF做过道区间取模...差不多, 只有开方, 那么每个数开方次数也是有限的(0,1时就会停止), 最大的数10^9开方10+次也就不会动了.那么 ...

  2. GSS4 - Can you answer these queries IV &vert;&vert; luogu4145上帝造题的七分钟2 &sol; 花神游历各国 &lpar;线段树&rpar;

    GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...

  3. bzoj3211 花神游历各国 线段树,势能分析

    [bzoj3211]花神游历各国 2014年3月17日2,7230 Description   Input   Output 每次x=1时,每行一个整数,表示这次旅行的开心度 Sample Input ...

  4. bzoj3211&colon; 花神游历各国&lpar;线段树&rpar; 同codevs2492

    3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 3628  Solved: 1326[Submit][Status][Discu ...

  5. BZOJ 3038&colon; 上帝造题的七分钟2 &sol; BZOJ 3211&colon; 花神游历各国 &lpar;线段树区间开平方&rpar;

    题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...

  6. bzoj3211花神游历各国 线段树

    3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 4252  Solved: 1547[Submit][Status][Discu ...

  7. BZOJ3211&colon;花神游历各国&lpar;线段树&rpar;

    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 ...

  8. BZOJ3211花神游历各国-线段树&amp&semi;树状数组-&lpar;HDU4027同类型&rpar;

    (有任何问题欢迎留言或私聊 && 欢迎交流讨论哦 题意:BZOJ HDU  原题目描述在最下面.  两种操作,1:把区间的数字开方一次,2:区间求和. 思路: 线段树:  显然不能暴力 ...

  9. day1 晚上 P4145 上帝造题的七分钟2 &sol; 花神游历各国 线段树

    #include<iostream> #include<cstdio> #include<cmath> using namespace std; ; struct ...

随机推荐

  1. 《Head First Servlet JSP》学习笔记

  2. requirejs 优化压缩

    1 配置node环境 2 配置built.js文档 3 执行命令node r.js -o built.js 文件目录: <!DOCTYPE HTML> <html lang=&quo ...

  3. StringBuilder是不是线程安全的?

    测试条件: 开启2个并行执行任务,往同一个StringBuilder对象写入值 测试代码: ; static StringBuilder sbIsThreadSafe = new StringBuil ...

  4. php代理

    有些网上接口请求需要用代理 php代码 <?php header('Access-Control-Allow-Origin:*'); $url=$_POST['urlString']; $res ...

  5. 关于ckeditor5设置高度

    在管理端模板AdminBSBMaterialDesign-master里发现一个比百度编辑器看起来更高大上的编辑器:ckeditor.模板中使用的是版本4,自己在官网上下载了最新版本.在之前的版本,使 ...

  6. ONOS架构-概览

    这个是阅读https://wiki.onosproject.org/display/ONOS/Architecture+Guide是顺便翻译的,目前断断续续在阅读,今天先贴一部分 概览 基于osgi, ...

  7. FZU 2150 Fire Game(点火游戏)

    FZU 2150 Fire Game(点火游戏) Time Limit: 1000 mSec    Memory Limit : 32768 KB Problem Description - 题目描述 ...

  8. 亚马逊aws 一个实例双网卡-两个弹性ip设置

    一个实例默认只有1个网络接口: 步骤一.创建一个新的网络接口,附加到实例. 步骤二.手动添加路由 增加两个路由表,为后续的双网关做点小准备: vim /etc/iproute2/rt_tables 添 ...

  9. ES配置文件中文版

    ##################### Elasticsearch Configuration Example ##################### # This file contains ...

  10. FLume监控文件夹,将数据发送给Kafka以及HDFS的配置文件详解

    详细配置文件flume-conf.properties如下: ############################################ # producer config ###### ...