Can you answer these queries III
2024-09-01 14:49:27
Can you answer these queries III
题目:洛谷 SPOJ
【题目描述】
给定长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:
1.“0 x y”,把A[x]改成y;
2.“1 x y”,查询区间[x,y]中的最大连续子段和。
【输入格式】
第一行,N;
第二行,N个数,即A[1]...A[N];
第三行,M;
第4至第M+3行,每行三个整数,分别表示“0或1”,x,y,即指令。
【输出格式】
i行,i表示“1 x y”的数量,每行1个整数,即指令2的答案。
【数据规模】
N,M<=50000。
解析
查询区间最大连续子段和,显然可以用线段树维护序列。
先分析一下,在线段树中,对于查询的每个区间[x,y],会有以下两种情况:
1、如图所示,区间刚好在一个子树中,只需查询该子树的区间最大连续子段和即可;
2、如图所示,区间一部分在左子树中,另一部分在右子树中,对于这种情况,该区间的最大连续子段和为左子树的最大后缀和加上右子树的最大前缀和。
考虑完所有情况后,只需套上线段树模板再稍作修改即可。
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
struct rec{
int l,r,maxn,lmax,rmax,sum;//lmax最大前缀和,rmax最大后缀和
}t[];
int n,m,a[];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].sum=t[p].lmax=t[p].rmax=t[p].maxn=a[l];
return ;
}
int mid=(l+r)/;
build(p*,l,mid);
build(p*+,mid+,r);
t[p].sum=t[p*].sum+t[p*+].sum;
t[p].lmax=max(t[p*].lmax,t[p*].sum+t[p*+].lmax);
t[p].rmax=max(t[p*+].rmax,t[p*+].sum+t[p*].rmax);
t[p].maxn=max(t[p*].rmax+t[p*+].lmax,max(t[p*].maxn,t[p*+].maxn));
return ;
}
void change(int p,int x,int v)
{
if(t[p].l==t[p].r)
{
t[p].sum=t[p].rmax=t[p].lmax=t[p].maxn=v;
return ;
}
int mid=(t[p].l+t[p].r)/;
if(x<=mid) change(p*,x,v);
else change(p*+,x,v);
t[p].sum=t[p*].sum+t[p*+].sum;
t[p].lmax=max(t[p*].lmax,t[p*].sum+t[p*+].lmax);
t[p].rmax=max(t[p*+].rmax,t[p*+].sum+t[p*].rmax);
t[p].maxn=max(t[p*].rmax+t[p*+].lmax,max(t[p*].maxn,t[p*+].maxn));
}
rec ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r) return t[p];
rec a,b,ans;
a.sum=a.lmax=a.rmax=a.maxn=b.sum=b.lmax=b.rmax=b.maxn=0xcfcfcfcf;
ans.sum=;
int mid=(t[p].l+t[p].r)/;
if(l<=mid)
{
a=ask(p*,l,r);
ans.sum+=a.sum;
}
if(r>mid)
{
b=ask(p*+,l,r);
ans.sum+=b.sum;
}
ans.maxn=max(max(a.maxn,b.maxn),a.rmax+b.lmax); //注意负数
ans.lmax=max(a.lmax,a.sum+b.lmax);
ans.rmax=max(b.rmax,b.sum+a.rmax);
if(l>mid) ans.lmax=max(ans.lmax,b.lmax);
if(r<=mid) ans.rmax=max(ans.rmax,a.rmax);
//分类讨论
return ans;
}
int main()
{
int c,l,r;
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
build(,,n);
cin>>m;
for(int i=;i<=m;i++)
{
cin>>c>>l>>r;
if(c==) change(,l,r);
else cout<<ask(,l,r).maxn<<endl;
}
return ;
}
最新文章
- javascript中的闭包、模块与模块加载
- mvc图片上传到服务器
- 自定义tab在地图进行分页显示
- android调试工具DDMS
- Hadoop-安装过程-单虚拟机版(伪分布式)(Ubuntu13.04版本下安装)
- 宝马-中国官方网站服务站点信息爬去记录(解析json中数据)
- IOS开发几何类方法 CGGeometry.h文件
- 在不同版本号hdfs集群之间转移数据
- 新秀系列C/C++经典问题(四)
- 基于PaaS和SaaS研发的商业云平台实战 转 (今后所有的IT行业会持续集成,往虚拟化方向更快更深的发展,商业化才是这些技术的最终目的)
- 如何修改Xampp服务器上的mysql密码
- Oracle安装步骤
- HighCharts之2D堆柱状图
- ThinkPHP5+Apicloud+vue商城APP实战
- MySQL的随机数函数rand()的使用技巧
- 第11月第14天 opengl yuv beginners-tutorials
- 简单理解IoC与DI
- 根据wsdl,基于wsimport生成代码的客户端
- 微信小程序获取当前经纬度并逆解析地址代码
- linux之JDK安装
热门文章
- java封装返回结果应用 利用反射机制 返回结果以及错误信息
- python3监控系统资源最终版(获取CPU,内存,磁盘,网卡等信息),返回json格式。
- [APIO2017]商旅——分数优化+floyd+SPFA判负环+二分答案
- Oracle虚拟机 与 windows配置
- maven手动将jar包导入到本地仓库(支持多个仓库选择)
- Tosca TestCases: Update all,Checkin all,Checkout,Checkout Tree
- LoadRunner11下载、安装与破解
- VS下设置dll环境变量目录的方法
- 解压命令unzip常用方法汇总
- 24 Flutter官方推荐的状态管理库provider的深入使用、初始化修改状态、父子组件同步状态