首页 > 代码库 > SPOJ GSS3 Can you answer these queries III
SPOJ GSS3 Can you answer these queries III
| 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:41 2 3 441 1 30 3 -31 2 41 3 3Output:64-3Hint
| 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 小白逛公园
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define lc rt<<1 8 #define rc rt<<1|1 9 using namespace std;10 const int mxn=100010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15 return x*f;16 }17 int n,m;18 int data[mxn];19 struct node{20 int mx;21 int ml,mr;22 int smm;23 }t[mxn<<2],tmp0;24 void push_up(int l,int r,int rt){25 t[rt].smm=t[lc].smm+t[rc].smm;26 t[rt].mx=max(t[lc].mx,t[rc].mx);27 t[rt].mx=max(t[lc].mr+t[rc].ml,t[rt].mx);28 t[rt].ml=max(t[lc].ml,t[lc].smm+t[rc].ml);29 t[rt].mr=max(t[rc].mr,t[rc].smm+t[lc].mr);30 return;31 }32 void Build(int l,int r,int rt){33 if(l==r){t[rt].mx=t[rt].ml=t[rt].mr=data[l];t[rt].smm=data[l];return;}34 int mid=(l+r)>>1;35 Build(l,mid,lc);36 Build(mid+1,r,rc);37 push_up(l,r,rt);38 return;39 }40 void change(int p,int v,int l,int r,int rt){41 if(l==r){42 if(p==l){t[rt].ml=t[rt].mr=t[rt].mx=t[rt].smm=v;}43 return;44 }45 int mid=(l+r)>>1;46 if(p<=mid)change(p,v,l,mid,lc);47 else change(p,v,mid+1,r,rc);48 push_up(l,r,rt);49 return;50 }51 node query(int L,int R,int l,int r,int rt){52 // printf("%d %d %d %d %d\n",L,R,l,r,rt);53 if(L<=l && r<=R){return t[rt];}54 int mid=(l+r)>>1;55 node res1;56 if(L<=mid)res1=query(L,R,l,mid,lc);57 else res1=tmp0;58 node res2;59 if(R>mid)res2=query(L,R,mid+1,r,rc);60 else res2=tmp0;61 node res={0};62 res.smm=res1.smm+res2.smm;63 res.mx=max(res1.mx,res2.mx);64 res.mx=max(res.mx,res1.mr+res2.ml);65 res.ml=max(res1.ml,res1.smm+res2.ml);66 res.mr=max(res2.mr,res2.smm+res1.mr);67 return res;68 }69 int main(){70 n=read();71 int i,j,x,y,k;72 for(i=1;i<=n;i++)data[i]=read();73 Build(1,n,1);74 tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=0;75 m=read();76 for(i=1;i<=m;i++){77 k=read();x=read();y=read();78 if(k){79 if(x>y)swap(x,y);80 printf("%d\n",query(x,y,1,n,1).mx);81 }82 else change(x,y,1,n,1);83 }84 return 0;85 }
SPOJ GSS3 Can you answer these queries III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。