HDOJ-4027(线段树+区间更新(每个节点更新的值不同))
2024-09-01 10:41:36
Can You answer these queries?
HDOJ-4027
- 这道题目和前面做的题目略有不同。以前的题目区间更新的时候都是统一更新的,也就是更新相同的值。但是这里不一样,这里更新的每个叶子结点改变不同。
- 考虑到数字最大也就64位,所以就算加上开根号的操作,也就最多开7次,所以这里可以转移到update函数中,每次走到叶子结点的时候进行开根号的操作。
- 在update函数中还有一个细节需要注意,那就是当当前结点所包含的所有叶子结点都是1的时候,就可以不用往下更新了,直接返回。
- query函数还是和以前的一样,没有新的东西。
- 针对这题,题目的题干还需要注意,输出的格式。还有就是x,y没有明确说是小于关系,故需要排序。
//区间修改(不同于统一修改,这里是区间中每一项修改的值都不一样)和区间查询
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100005;
int n,m;
long long dur[maxn];
long long sums[maxn<<2];
void pushup(int id,int l,int r){
int lc=id<<1;
int rc=id<<1|1;
sums[id]=sums[lc]+sums[rc];
}
void build(int id,int l,int r){
if(l==r){
sums[id]=dur[l];
return;
}
int mid=(l+r)>>1;
int lc=id<<1;
int rc=id<<1|1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(id,l,r);
}
void update(int id,int l,int r,int p,int q){
if(sums[id]==r-l+1){//当结点覆盖的叶子结点全是1,也就是说sum等于覆盖的长度时返回,不用继续计算。
return;
}
if(l==r){
sums[id]=sqrt(sums[id]);
return;
}
int mid=(l+r)>>1;
if(p<=mid){
update(id<<1,l,mid,p,q);
}
if(q>mid){
update(id<<1|1,mid+1,r,p,q);
}
pushup(id,l,r);
}
long long query(int id,int l,int r,int p,int q){
long long sum=0;
if(p<=l&&q>=r){
return sum=sums[id];
}
int mid=(l+r)>>1;
int lc=id<<1;
int rc=id<<1|1;
if(p<=mid){
sum+=query(lc,l,mid,p,q);
}
if(q>mid){
sum+=query(rc,mid+1,r,p,q);
}
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int k=0;
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>dur[i];
}
build(1,1,n);
cin>>m;
cout<<"Case #"<<++k<<":"<<endl;
for(int i=0;i<m;i++){
int t,p,q;
cin>>t>>p>>q;//不保证p<q
int temp=p;
p=min(p,q);
q=max(temp,q);
if(t==0){//update
update(1,1,n,p,q);
}else{//query
cout<<query(1,1,n,p,q)<<endl;
}
}
cout<<endl;
}
return 0;
}
最新文章
- android 腾讯x5内核 浏览器
- 【枚举】POJ 3279
- Linux Shell 重定向与管道【转帖】
- CSS2中基本属性的介绍
- CSV的导入导出
- html、css、javascript、JSP 、xml学习顺序应该是怎样的呢?
- Redis部分数据结构方法小结
- 使用GCD
- ASP.NET Web API上实现 Web Socket
- Core Data (一)备
- JavaScript(10)——Ajax以及跨域处理
- js导出excel文件
- LeetCode题解之Sum Root to Leaf Numbers
- Python模块初识
- [Algorithm] Warm-up puzzles
- mysql判断两个时间段是否有交集
- day3 python 阿狸的进阶之路
- iview,用render函数渲染
- POJ 1556 - The Doors - [平面几何+建图spfa最短路]
- sublime 对vue的高亮显示
热门文章
- Codeforces Round #575 (Div. 3) D2. RGB Substring (hard version)
- 计蒜客-T1271 完美K倍子数组
- 牛客练习赛70 B.拼凑 (序列自动机)
- PowerShell随笔7 -- Try Catch
- Python_小程序
- select用法&;原理详解(源码剖析)(转)
- printf,sprintf,fprintf的区别与联系
- springboot demo(二)web开发demo
- XCTF攻防世界web进阶练习—mfw
- ES6 Generator vs ES6 async/await