GSS3 - Can you answer these queries III
题意翻译
nnn 个数, qqq 次操作
操作0 x y
把 AxA_xAx 修改为 yyy
操作1 l r
询问区间 [l,r][l, r][l,r] 的最大子段和
感谢 @Edgration 提供的翻译
题目描述
You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输入输出格式
输入格式:
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输出格式:
For each query, print an integer as the problem required.
输入输出样例
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
6
4
-3 提交地址 : luogu SP1716
spoj; 分析:
线段树水题; 用线段树维护四个值 : 这一区间的最大子段和, 这一区间的从最左端开始的最大子段和, 从右端开始的最大子段和,还有这一段的和;
怎么维护?
t[o].sum = t[ls(o)].sum + t[rs(o)].sum;
t[o].lsum = max(t[ls(o)].lsum, t[ls(o)].sum + t[rs(o)].lsum);
t[o].rsum = max(t[rs(o)].rsum, t[rs(o)].sum + t[ls(o)].rsum);
t[o].dat = max(t[ls(o)].rsum + t[rs(o)].lsum, max(t[ls(o)].dat, t[rs(o)].dat));
就解释一个:你左端开始的最大子段和一定是你左二子的左端点开始的最大子段和, 还有左二子全选加上右儿子的左端开始的最大子段和;
其他的都大同小异;
一样的按照普通线段树写;
主要讲讲查询操作;
因为我们要找一个连续的序列,而不是每个dat取max;
所以我们要维护一个前缀和qzh;
因为我们维护的是前缀和, 所以每次可以用 qzh+t[o].lsum 和 t[o].dat 取max来更新ans;
然后我们再改变qzh的值 在 qzh + t[o].sum 和 t[o].rsum中取max;
代码奉上:
//zZhBr
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long inline int read()
{
int res=;bool flag=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')flag=;ch=getchar();};
while(isdigit(ch)){res=(res<<)+(res<<)+(ch-'');ch=getchar();}
return flag?-res:res;
} const int N = ; int n, a[N], m;
int ans, qzh; struct Segment
{
int ls, rs;
int l, r;
int sum;
int lsum, rsum;
int dat;
}t[N<<];
int cnt = ;
int root;
#define ls(x) t[x].ls
#define rs(x) t[x].rs inline void pushup(int o)
{
t[o].l = t[ls(o)].l, t[o].r = t[rs(o)].r;
t[o].sum = t[ls(o)].sum + t[rs(o)].sum;
t[o].lsum = max(t[ls(o)].lsum, t[ls(o)].sum + t[rs(o)].lsum);
t[o].rsum = max(t[rs(o)].rsum, t[rs(o)].sum + t[ls(o)].rsum);
t[o].dat = max(t[ls(o)].rsum + t[rs(o)].lsum, max(t[ls(o)].dat, t[rs(o)].dat));
} inline void build(int l, int r, int o)
{
if (l == r)
{
t[o].sum = a[l];
t[o].lsum = a[l];
t[o].rsum = a[l];
t[o].dat = a[l];
t[o].l = t[o].r = l;
return;
} int mid = l + r >> ;
t[o].ls = cnt++;
t[o].rs = cnt++;
build(l, mid, ls(o));
build(mid + , r, rs(o));
pushup(o);
} inline void change(int o, int x, int v)
{
if (t[o].l == t[o].r)
{
t[o].sum = v;
t[o].dat = v;
t[o].lsum = t[o].rsum = v;
return;
} int mid = t[o].l + t[o].r >> ; if (x <= mid) change(ls(o), x, v);
else change(rs(o), x, v);
pushup(o);
} inline void query(int o, int li, int ri)
{
if (li <= t[o].l and ri >= t[o].r)
{
ans = max(ans, max(qzh + t[o].lsum, t[o].dat));
qzh = max(qzh + t[o].sum, t[o].rsum);
return;
}
int res = ;
int mid = t[o].r + t[o].l >> ;
if (li <= mid) query(ls(o), li, ri);
if (ri > mid) query(rs(o), li, ri);
} signed main()
{
n = read();
for (register int i = ; i <= n ; i ++) a[i] = read();
m = read();
root = cnt++;
build(, n, root); while (m--)
{
int opt = read();
int x = read(), y = read(); if (opt == )
{
change(root, x, y);
}
else
{
ans = -1e9, qzh = -1e9;
query(root, x, y);
printf("%lld\n", ans);
}
} return ; }
最新文章
- FragmentTabHost的基本用法
- ORACLE 9i 数据库体系结构图
- js/css在html文档中的引用外部文件方式对比
- BZOJ3218 UOJ#77 A+B Problem(最小割+主席树)
- MySQL 基础语句的练习2
- spark 加载文件
- iOS系统消息
- jQuery File Upload跨域上传
- SDUT 3345 数据结构实验之二叉树六:哈夫曼编码
- java中接口的定义与实现
- nagios plugins之 check_http
- Oracle索引扫描算法
- BZOJ 3362 POJ 1984 Navigation Nightmare 并与正确集中检查
- 如何一步一步用DDD设计一个电商网站(十二)—— 提交并生成订单
- light oj 1254 - Prison Break 最短路
- 通过SecureCRT连接虚拟机
- SAP 生产订单变更管理 OCM Order Changement Management
- springboot创建统一异常拦截器全局处理 异常
- ThinkNet终于见面了
- Cell complex单元复合形
热门文章
- 基于通用jar、动态配置、组件编排的会员任务中心系统设计
- Docker常用命令小记
- Appium+python自动化(三十八) - Appium自动化测试框架综合实践 - 框架简介-助你冲击高薪,迎娶白富美(超详解)
- JS中3种风格的For循环有什么异同?
- 提交第一个spark作业到集群运行
- Spring 梳理 - AOP那些学术概念—通知、增强处理连接点(JoinPoint)切面(Aspect)
- rt.jar包添加源文件只需要关联到已安装对应jdk目录下source.zip源码文件即可
- 无广告版本Flash player 一枚,需要的拿走~
- Hbase入门(四)——表结构设计-RowKey
- python——pyinstaller踩的坑 UnicodeDecodeError