SPOJ GSS3 Can you answer these queries III
2024-08-26 13:35:16
Time Limit: 330MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
Description
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 }.
Input
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 }.
Output
For each query, print an integer as the problem required.
Example
Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3 Output:
6
4
-3
Hint
Added by: | Bin Jin |
Date: | 2007-08-03 |
Time limit: | 0.330s |
Source limit: | 5000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C++ 5 |
Resource: | own problem |
单点修改,询问区间内最大连续字段和。
@TYVJ P1427 小白逛公园
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lc rt<<1
#define rc rt<<1|1
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int data[mxn];
struct node{
int mx;
int ml,mr;
int smm;
}t[mxn<<],tmp0;
void push_up(int l,int r,int rt){
t[rt].smm=t[lc].smm+t[rc].smm;
t[rt].mx=max(t[lc].mx,t[rc].mx);
t[rt].mx=max(t[lc].mr+t[rc].ml,t[rt].mx);
t[rt].ml=max(t[lc].ml,t[lc].smm+t[rc].ml);
t[rt].mr=max(t[rc].mr,t[rc].smm+t[lc].mr);
return;
}
void Build(int l,int r,int rt){
if(l==r){t[rt].mx=t[rt].ml=t[rt].mr=data[l];t[rt].smm=data[l];return;}
int mid=(l+r)>>;
Build(l,mid,lc);
Build(mid+,r,rc);
push_up(l,r,rt);
return;
}
void change(int p,int v,int l,int r,int rt){
if(l==r){
if(p==l){t[rt].ml=t[rt].mr=t[rt].mx=t[rt].smm=v;}
return;
}
int mid=(l+r)>>;
if(p<=mid)change(p,v,l,mid,lc);
else change(p,v,mid+,r,rc);
push_up(l,r,rt);
return;
}
node query(int L,int R,int l,int r,int rt){
// printf("%d %d %d %d %d\n",L,R,l,r,rt);
if(L<=l && r<=R){return t[rt];}
int mid=(l+r)>>;
node res1;
if(L<=mid)res1=query(L,R,l,mid,lc);
else res1=tmp0;
node res2;
if(R>mid)res2=query(L,R,mid+,r,rc);
else res2=tmp0;
node res={};
res.smm=res1.smm+res2.smm;
res.mx=max(res1.mx,res2.mx);
res.mx=max(res.mx,res1.mr+res2.ml);
res.ml=max(res1.ml,res1.smm+res2.ml);
res.mr=max(res2.mr,res2.smm+res1.mr);
return res;
}
int main(){
n=read();
int i,j,x,y,k;
for(i=;i<=n;i++)data[i]=read();
Build(,n,);
tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=;
m=read();
for(i=;i<=m;i++){
k=read();x=read();y=read();
if(k){
if(x>y)swap(x,y);
printf("%d\n",query(x,y,,n,).mx);
}
else change(x,y,,n,);
}
return ;
}
最新文章
- 【.net 深呼吸】程序集的热更新
- Linux下安装Java环境配置步骤详述
- Hadoop集群datanode磁盘不均衡的解决方案
- CSS3制作同心圆进度条
- WdatePicker 开始日期不能大于结束日期,结束时间不能小于开始时间
- 关于微信扫描二维码下载apk文件的细节设计
- Windows下配置PHP支持LDAP扩展方法(wampserver)
- Codeforces 350B Resort
- 浅谈身为小白学习Linux系统的四点实用建议
- how tomcat works 5 servlet容器 下
- 分布式存储ceph——(3)ceph常用命令
- boost--文件、目录操作
- JxBrowser之三:常用函数setNetworkDelegate
- while 循环,格式化输出,运算符(not,and,or)
- haproxy [WARNING] 312/111530 (17395) : config : &#39;option forwardfor&#39; ignored for frontend &#39;harbor_login&#39; as it requires HTTP mode.
- linespace函数
- php十行代码将xml转成数组
- NET Framework 4.0无法安装!
- PigGo+Github图床,编写本地markdown
- 可编辑表格(Editable Table)
热门文章
- [资料]mysql实现地理位置搜索
- 网络/运维工程师visio2013模具图标 绘制漂亮的网络拓扑图 狮子XL工程师美学思想
- http://kb.cnblogs.com/zt/ef/
- jboss eap 6.3 集群(cluster)-Session 复制(Replication)
- 一例完整的websocket实现群聊demo
- ModernUI教程:使用WPF4.0
- 最短判断IE的办法
- hihocoder 1260
- webpack 教程资源收集
- C++11的default和delete关键字