105 条题解
-
10
mangoyang LV 8 @ 2017-07-12 18:33:21
因为要维护区间最大连续子段和，我们可以考虑用线段树维护
分析得出，一个区间的最大子段和等于MAX(左儿子(以下用lson)的最大子段和,右儿子(以下用rson)的最大子段和,左右儿子合并时的中间一段的最大子段和)
前两个项很好维护，但要注意的是中间的子段和..
观察发现，中间的子段和==以lson的右边界为端点向左扫的最大子段和+rson的左边界为端点向右扫的最大子段和；所以只需要在维护最大子段和的同时，维护以左右端点为起点的两个方向的最大子段和
实际上这两个最大字段和又等于(以lson为例，rson同理)MAX(lson的最大向左子段和,lson的总和+以rson左端点向右推的最大子段和)
再维护一个sum就可以解决这一问题，本蒟蒻太弱了，所以打的特别慢，膜拜各位大佬#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define INF (0x7f7f7f7f) #define Max(a,b) ((a)>(b)?(a):(b)) #define N (500005) #define lson (u<<1) #define rson (u<<1|1) using namespace std; inline void Swap(int &x,int &y){int tmp=x; x=y, y=tmp;} int a[N],n,m; struct segment_tree{ struct node{ int keyL,keyR,key,sum; inline node(){keyL=keyR=key=sum=0;} inline node(int a,int b,int c,int d):keyL(a),keyR(b),key(c),sum(d){} }T[4*N]; inline void pushup(int u){ T[u].keyL=Max(T[lson].keyL,T[lson].sum+T[rson].keyL); T[u].keyR=Max(T[rson].keyR,T[rson].sum+T[lson].keyR); T[u].key=Max(Max(T[lson].key,T[rson].key),T[lson].keyR+T[rson].keyL); T[u].sum=T[lson].sum+T[rson].sum; } void build(int u,int l,int r){ if(l==r){T[u].keyL=T[u].keyR=T[u].key=T[u].sum=a[l]; return;} int mid=(l+r)>>1; build(lson,l,mid), build(rson,mid+1,r), pushup(u); } void modify(int u,int l,int r,int pos,int cont){ if(l==r){T[u].keyL=T[u].keyR=T[u].key=T[u].sum=cont; return;} int mid=(l+r)>>1; if(pos<=mid)modify(lson,l,mid,pos,cont); else modify(rson,mid+1,r,pos,cont); pushup(u); } node query(int u,int l,int r,int L,int R){ if(l>=L&&r<=R)return node(T[u].keyL,T[u].keyR,T[u].key,T[u].sum); int mid=(l+r)>>1,opt=0; node left,right; if(L<=mid)left=query(lson,l,mid,L,R),opt+=1; if(mid<R)right=query(rson,mid+1,r,L,R),opt+=2; if(opt==1)return left; if(opt==2)return right; node ans; ans.keyL=Max(left.keyL,left.sum+right.keyL); ans.keyR=Max(right.keyR,right.sum+left.keyR); ans.key=Max(Max(left.key,right.key),left.keyR+right.keyL); ans.sum=left.sum+right.sum; return ans; } }van; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); van.build(1,1,n); for(int i=1;i<=m;i++){ int opt,x,y; scanf("%d",&opt); if(opt==1){ scanf("%d%d",&x,&y); if(x>y)Swap(x,y); printf("%d\n",van.query(1,1,n,x,y).key); } if(opt==2){ scanf("%d%d",&x,&y); van.modify(1,1,n,x,y); } } return 0; } -
6
/* 线段树的题啊…… 还有输入中a可能大于b，要判断并交换。 这里我们用到了一种分治的思想 所以我们可以用这个结构体来储存一个区间 struct node { int left,right,maxv,sum; } 其中left表示从左端点向右能达到的最大值 right表示从右端点到右所能达到的最大值 maxv就是我们要求的 即整个区间中能达到的最大连续和值 sum自然就是所有区间内所有数的和了 在最大连续子序列的和中 我们有动态规划好写+O(n)的算法 所以有的时候就忽略了我们的O(nlogn)的分治算法 我们看这么几个式子即renew函数更新节点的附加信息的函数 tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; tree[o].left=max(tree[o<<1].left,tree[o<<1].sum+tree[o<<1|1].left); tree[o].right=max(tree[o<<1|1].right,tree[o<<1|1].sum+tree[o<<1].right); tree[o].maxv=max(tree[o<<1].right+tree[o<<1|1].left,max(tree[o<<1].maxv,tree[o<<1|1].maxv)); 第一个sum不言而喻地球人都知道 第二个left我们可以知道是要从左端点向右 那么我们分治分成两半 一定有要么是左半端点向右延伸没有到达中点 要么是左端端点延伸到达了右部分 所以这个时候肯定就是选取了全部的左边加上右端的left 第三个也是一样的道理咯 这里就不赘说了 第四个maxv我们就是和O(nlogn)算法的思路一样了 我们知道一个最大连续和的子序列 要么是左半段的最大和 要么就是右半段的最大和 要么就是横跨左右的最大和 那么我们对应的就是tree[o<<1].maxv tree[o<<1|1].maxv tree[o<<1].right+tree[o<<1|1].left 然后就取下最大值就好了 这样我们就完成了节点的值的维护方法咯 那么我们就可以用线段树来解决一个个区间问题了 这个因为打分是只改变一个的 所以就是简单的单点修改问题OTZ 然后直接狂撸就好了 ORZ%%%窝好弱啊 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=500010; struct node { int left,right,maxv,sum; }tree[MAXN<<2]; int n,m; void renew(int o) { tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; tree[o].left=max(tree[o<<1].left,tree[o<<1].sum+tree[o<<1|1].left); tree[o].right=max(tree[o<<1|1].right,tree[o<<1|1].sum+tree[o<<1].right); tree[o].maxv=max(tree[o<<1].right+tree[o<<1|1].left,max(tree[o<<1].maxv,tree[o<<1|1].maxv)); } void change(int o,int l,int r,int a,int c)//c为修改的值,a是要单点修改的点，o节点编号,l,r对应节点区间 { if(l==r) { tree[o].left=tree[o].right=tree[o].maxv=tree[o].sum=c; return; } int mid=(l+r)>>1; if(a<=mid) change(o<<1,l,mid,a,c); else change(o<<1|1,mid+1,r,a,c); renew(o); } node query(int o,int l,int r,int a,int b)//o节点编号,l r是节点对应区间,a,b为要查找的区间 { if(a<=l&&b>=r) return tree[o]; int mid=(l+r)>>1; if(b<=mid)//查询区间全在左儿子 return query(o<<1,l,mid,a,b); else if(a>mid)//查询区间全在右儿子 return query(o<<1|1,mid+1,r,a,b); else//左右儿子均有，需把左右儿子组合起来更新，再返回 { node res,res1,res2; res1=query(o<<1,l,mid,a,b); res2=query(o<<1|1,mid+1,r,a,b); res.sum=res1.sum+res2.sum; res.left=max(res1.left,res1.sum+res2.left); res.right=max(res2.right,res2.sum+res1.right); res.maxv=max(res1.right+res2.left,max(res1.maxv,res2.maxv)); return res; } } int main() { int x,op,a,b; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; change(1,1,n,i,x); } while(m--) { cin>>op>>a>>b; if(op==1) { if(a>b) swap(a,b); printf("%d\n",query(1,1,n,a,b).maxv); } else change(1,1,n,a,b); } return 0; } -
3
正在加载...99% LV 8 @ 2017-03-25 12:05:01
JRX2015U43：
#include<bits/stdc++.h> using namespace std; const int INF=(1<<30)-1; const int maxn=500000; struct Edge{ int ml,mr,sum,maxs; }; int data[maxn*4+5]={0},l[maxn*4+5]={0},r[maxn*4+5]={0},ml[maxn*4+5]={0},mr[maxn*4+5]={0},sum[maxn*4+5]={0},maxs[maxn*4+5]={0}; void Pushup(int v){ ml[v]=max(ml[l[v]],sum[l[v]]+ml[r[v]]); mr[v]=max(mr[r[v]],sum[r[v]]+mr[l[v]]); sum[v]=sum[l[v]]+sum[r[v]]; maxs[v]=max(max(maxs[l[v]],maxs[r[v]]),mr[l[v]]+ml[r[v]]); } void build(int v,int x,int y){ if (x==y){ sum[v]=ml[v]=data[x]; mr[v]=maxs[v]=ml[v]; return; } int mid=(x+y)>>1; l[v]=v*2,r[v]=v*2+1; build(l[v],x,mid);build(r[v],mid+1,y); Pushup(v); } void Updata(int v,int x,int y,int p,int s){ if (x==y){ sum[v]=ml[v]=s; mr[v]=maxs[v]=ml[v]; return; } int mid=(x+y)>>1; if (p<=mid) Updata(v*2,x,mid,p,s); else Updata(v*2+1,mid+1,y,p,s); Pushup(v); } Edge Query(int v,int x,int y,int a,int b){ if (a<=x&&b>=y){ Edge ans; ans.ml=ml[v]; ans.mr=mr[v]; ans.sum=sum[v]; ans.maxs=maxs[v]; return ans; } int mid=(x+y)>>1; Edge ansl,ansr; if (a<=mid) ansl=Query(v*2,x,mid,a,b); else ansl.sum=-INF; if (b>mid) ansr=Query(v*2+1,mid+1,y,a,b); else ansr.sum=-INF; if (ansl.sum==-INF) return ansr; if (ansr.sum==-INF) return ansl; Edge ans; ans.ml=max(ansl.ml,ansl.sum+ansr.ml); ans.mr=max(ansr.mr,ansr.sum+ansl.mr); ans.sum=ansl.sum+ansr.sum; ans.maxs=max(max(ansl.maxs,ansr.maxs),ansl.mr+ansr.ml); return ans; } int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&data[i]); build(1,1,n); while (m--){ int k,x,y; scanf("%d%d%d",&k,&x,&y); if (k==1){ if (x>y) swap(x,y); printf("%d\n",Query(1,1,n,x,y).maxs); } else Updata(1,1,n,x,y); } } -
1
Sky1231 (sky1231) LV 10 @ 2020-10-23 00:37:04
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; namespace dts { class st_node { public: int l,r,mid; int lans=0,rans=0,ans=0,sum=0; int iflz=0,numlz; int len() { return r-l+1; } }; st_node st[(1<<21)+2]; #define lc(now) ((now)<<1) #define rc(now) ((now)<<1|1) st_node merge(st_node li,st_node ri) { st_node a; a.iflz=0; a.l=li.l,a.r=ri.r,a.mid=li.r; a.lans=max(li.lans,li.sum+ri.lans); a.rans=max(ri.rans,ri.sum+li.rans); a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans); a.sum=li.sum+ri.sum; return a; } void st_pushup(int now) { st[now]=merge(st[lc(now)],st[rc(now)]); } void st_update(int now,int l,int r,int val); void st_pushdown(int now) { if (st[now].iflz) { st_update(lc(now),st[now].l,st[now].mid,st[now].numlz); st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz); st[now].iflz=0; } } void st_update(int now,int l,int r,int val) { if (st[now].l==l&&r==st[now].r) { st[now].lans=st[now].rans=st[now].ans=max(val,st[now].len()*val); st[now].sum=st[now].len()*val; st[now].iflz=1,st[now].numlz=val; } else { st_pushdown(now); if (r<=st[now].mid) st_update(lc(now),l,r,val); else if (st[now].mid+1<=l) st_update(rc(now),l,r,val); else st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val); st_pushup(now); } } st_node st_ask(int now,int l,int r) { if (st[now].l==l&&r==st[now].r) return st[now]; else { st_pushdown(now); if (r<=st[now].mid) return st_ask(lc(now),l,r); else if (st[now].mid+1<=l) return st_ask(rc(now),l,r); else return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r)); } } void st_build(int now,int l,int r,int *a) { st[now].iflz=0; st[now].l=l,st[now].r=r; if (l<r) { st[now].mid=(l+r)>>1; st_build(lc(now),l,st[now].mid,a); st_build(rc(now),st[now].mid+1,r,a); st_pushup(now); } else st[now].lans=st[now].rans=st[now].ans=st[now].sum=a[l]; } int n,m,a[(1<<19)+1]; void main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); st_build(1,1,n,&a[0]); for (int i=1;i<=m;i++) { int K,a,b; scanf("%d%d%d",&K,&a,&b); if (K==1) printf("%d\n",st_ask(1,min(a,b),max(a,b)).ans); else if (K==2) st_update(1,a,a,b); } } } int main() { dts::main(); } -
1
这道题的题意是维护一个动态的带修改最大子段和。
我们发现这个最大子段和是可以通过一些维护更新由两个区间合并到一个区间的，所以可以用线段树维护。
具体怎样维护？
我们让tot[i]表示i这个节点代表区间的数的总和，lm[i]表示i这个节点代表区间从左端点开始（必须包括左端点）的最大子段和，rm[i]表示i这个节点代表区间从右端点开始（必须包括右端点）的最大子段和,ans[i]表示i这个节点代表区间的最大子段和。这样我们就可以合并两个区间的答案了。 具体的更新维护代码如下。void maintain(int x)
{
int ll=node[x].lc,rr=node[x].rc;
node[x].tot=node[ll].tot+node[rr].tot;//更新总和
node[x].lm=max(node[ll].lm,node[ll].tot+node[rr].lm);//更新左端点开始的最大子段和。两种情况分别是不跨过mid和跨过mid。
node[x].rm=max(node[rr].rm,node[rr].tot+node[ll].rm);//更新右端点开始的最大子段和。两种情况分别是不跨过mid和跨过mid。
node[x].ans=max(max(node[ll].ans,node[rr].ans),node[ll].rm+node[rr].lm);
}//更新最大子段和的答案。分三种情况：最大子段只在mid左边，跨过mid，只在mid右边。
代码#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
int l,r,lc,rc,lm,rm,ans,tot;
}node[4000005];
int n,m,k,x,y,cnt=0,a[500001];
void maintain(int x)//维护更新，合并答案
{
int ll=node[x].lc,rr=node[x].rc;
node[x].tot=node[ll].tot+node[rr].tot;
node[x].lm=max(node[ll].lm,node[ll].tot+node[rr].lm);
node[x].rm=max(node[rr].rm,node[rr].tot+node[ll].rm);
node[x].ans=max(max(node[ll].ans,node[rr].ans),node[ll].rm+node[rr].lm);
}
void build(int l,int r,int now)
{
node[now].l=l;
node[now].r=r;
if(l==r)
{
node[now].lm=node[now].rm=node[now].tot=node[now].ans=a[l];//赋初值
return;//不要忘记return
}
int mid=(l+r)>>1;
node[now].lc=2*now;
build(l,mid,node[now].lc);
node[now].rc=2*now+1;
build(mid+1,r,node[now].rc);
maintain(now);//合并答案
}
void update(int now,int to,int num)
{
int x=node[now].l,y=node[now].r;
if(x==y)
{
node[now].lm=node[now].rm=node[now].tot=node[now].ans=num;//修改
return;
}
int mid=(x+y)>>1;
if(to<=mid) update(node[now].lc,to,num);
else update(node[now].rc,to,num);
maintain(now);//合并答案
}
Node query(int now,int l,int r)
{
int x=node[now].l,y=node[now].r;
if(l<=x&&r>=y) return node[now];//当前节点在询问区间当中，直接返回答案。
int mid=(x+y)>>1,ll=node[now].lc,rr=node[now].rc;
if(r<=mid) return query(ll,l,r);
else if(l>mid) return query(rr,l,r);
else//询问区间跨过mid时要合并一下答案，思路与maintain函数中的差不多，在此不再赘述。
{
Node t,t1=query(ll,l,r),t2=query(rr,l,r);
t.lm=max(t1.lm,t1.tot+t2.lm);
t.rm=max(t2.rm,t2.tot+t1.rm);
t.ans=max(max(t1.ans,t2.ans),t1.rm+t2.lm);
return t;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&x,&y);
if(k==1)
{
if(x>y) swap(x,y);
printf("%d\n",query(1,x,y).ans);
}
else update(1,x,y);
}
return 0;
} -
0
#include <cstdio> #include <algorithm> using namespace std; struct Segtree { int parent; int sum; int lpark; int rpark; int lchild; int rchild; int lside; int rside; int maxv; }; int n, m; int start_s[500005]; int leaf[500005]; Segtree st[1500005]; int next_tree = 1; void calc(int tree) { st[tree].lside = max(st[st[tree].lchild].lside, st[st[tree].lchild].sum + st[st[tree].rchild].lside); st[tree].rside = max(st[st[tree].rchild].rside, st[st[tree].rchild].sum + st[st[tree].lchild].rside); st[tree].maxv = max(st[st[tree].lchild].maxv, max(st[st[tree].rchild].maxv, st[st[tree].lchild].rside + st[st[tree].rchild].lside)); st[tree].sum = st[st[tree].lchild].sum + st[st[tree].rchild].sum; } void calc_recursive(int tree) { calc(tree); if (st[tree].parent) { calc_recursive(st[tree].parent); } } int build_tree(int lp, int rp, int par) { int tree = next_tree++; st[tree].lpark = lp; st[tree].rpark = rp; st[tree].parent = par; if (lp == rp) { st[tree].lside = start_s[lp]; st[tree].rside = start_s[lp]; st[tree].maxv = start_s[lp]; st[tree].sum = start_s[lp]; leaf[lp] = tree; } else { st[tree].lchild = build_tree(lp, (lp + rp) / 2, tree); st[tree].rchild = build_tree((lp + rp) / 2 + 1, rp, tree); calc(tree); } return tree; } int find_lside(int tree, int maximum) { int retval; if (st[tree].lpark > maximum) return -1000000000; if (tree == 0) return 0; if (st[tree].rpark <= maximum) { retval = st[tree].lside; } else { if (maximum <= (st[tree].lpark + st[tree].rpark) / 2) { retval = find_lside(st[tree].lchild, maximum); } else { retval = max(find_lside(st[tree].lchild, maximum), st[st[tree].lchild].sum + find_lside(st[tree].rchild, maximum)); } } //printf("[%d %d] find_lside: %d\n", st[tree].lpark, st[tree].rpark, retval); return retval; } int find_rside(int tree, int minimum) { int retval; if (st[tree].rpark < minimum) return -1000000000; if (tree == 0) return 0; if (st[tree].lpark >= minimum) { retval = st[tree].rside; } else { if (minimum >= (st[tree].lpark + st[tree].rpark) / 2 + 1) { retval = find_rside(st[tree].rchild, minimum); } else { retval = max(find_rside(st[tree].rchild, minimum), st[st[tree].rchild].sum + find_rside(st[tree].lchild, minimum)); } } //printf("[%d %d] find_rside: %d\n", st[tree].lpark, st[tree].rpark, retval); return retval; } int op1(int tree, int lp, int rp, int a, int b) { //printf("[%d %d] op1\n", lp, rp); if (a > b) { int t = a; a = b; b = t; } if (b < lp || rp < a) return -1000000000; if (a <= lp && b >= rp) { return st[tree].maxv; } return max(max(op1(st[tree].lchild, lp, (lp + rp) / 2, a, b), op1(st[tree].rchild, (lp + rp) / 2 + 1, rp, a, b)), find_lside(st[tree].rchild, b) + find_rside(st[tree].lchild, a)); } void op2(int park, int score) { st[leaf[park]].sum = st[leaf[park]].lside = st[leaf[park]].rside = st[leaf[park]].maxv = score; if (park != 1) calc_recursive(st[leaf[park]].parent); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", start_s + i); } build_tree(1, n, 0); for (int i = 1; i <= m; i++) { int k, a, b; scanf("%d%d%d", &k, &a, &b); if (k == 1) { printf("%d\n", op1(1, 1, n, a, b)); } else { op2(a, b); } } return 0; } -
0
指针大法好......
#include <algorithm> #include <stdio.h> #include <string.h> using namespace std; const int MAXN=500000; const int MAXM=100000; struct Tree{ struct Node{ Node *lson,*rson; int l,r; int value,sum,lsum,rsum,maxsum; Node(int l,int r,Node *lson,Node *rson):l(l),r(r),lson(lson),rson(rson){} void maintain(){ sum=value; if(lson) sum+=lson->sum; if(rson) sum+=rson->sum; lsum=rsum=sum; if(lson){ lsum=max(lsum,lson->lsum); if(rson) lsum=max(lsum,lson->sum+rson->lsum); } if(rson){ rsum=max(rsum,rson->rsum); if(lson) rsum=max(rsum,rson->sum+lson->rsum); } maxsum=sum; maxsum=max(maxsum,lsum); maxsum=max(maxsum,rsum); if(lson) maxsum=max(maxsum,lson->maxsum); if(rson) maxsum=max(maxsum,rson->maxsum); if(lson && rson) maxsum=max(maxsum,lson->rsum+rson->lsum); } void query(int l,int r,int &sum,int &lsum,int &rsum,int &maxsum){ if(this->l>r || this->r<l) throw; else if(this->l>=l && this->r<=r){ sum=this->sum; lsum=this->lsum; rsum=this->rsum; maxsum=this->maxsum; }else{ int mid=this->l+this->r>>1; if(r<=mid) return lson->query(l,r,sum,lsum,rsum,maxsum); if(l>=mid+1) return rson->query(l,r,sum,lsum,rsum,maxsum); else{ int suml,lsuml,rsuml,maxsuml; int sumr,lsumr,rsumr,maxsumr; lson->query(l,r,suml,lsuml,rsuml,maxsuml); rson->query(l,r,sumr,lsumr,rsumr,maxsumr); maxsum=sum=suml+sumr; lsum=max(lsuml,suml+lsumr); rsum=max(rsumr,sumr+rsuml); maxsum=max(maxsum,maxsuml); maxsum=max(maxsum,maxsumr); maxsum=max(maxsum,lsumr+rsuml); } } } void update(int pos,int value){ if(this->l>pos || this->r<pos) return; else if(this->l==pos && this->r==pos) this->value=value,maintain(); else{ if(lson) lson->update(pos,value); if(rson) rson->update(pos,value); maintain(); } } }*root; Tree(int l,int r){ root=build(l,r); } Node *build(int l,int r){ if(l>r) return NULL; else if(l==r) return new Node(l,r,NULL,NULL); else return new Node(l,r,build(l,l+r>>1),build((l+r>>1)+1,r)); } void update(int pos,int value){ root->update(pos,value); } int query(int l,int r){ int sum,lsum,rsum,maxsum; root->query(l,r,sum,lsum,rsum,maxsum); return maxsum; } }; int main(){ int n,m; scanf("%d%d",&n,&m); Tree *T=new Tree(1,n); for(int i=1;i<=n;i++){ int value; scanf("%d",&value); T->update(i,value); } for(int i=1;i<=m;i++){ int op; scanf("%d",&op); if(op==1){ int l,r; scanf("%d%d",&l,&r); printf("%d\n",T->query(min(l,r),max(l,r))); }else{ int pos,value; scanf("%d%d",&pos,&value); T->update(pos,value); } } return 0; } -
0
#include<iostream> #include<cstdio> using namespace std; struct SGT {int l,r,lmxs,rmxs,mxs,s;SGT(){l=r=lmxs=rmxs=mxs=s=0;};} sgt[500010<<2]; int n,m; int da[500010]; void sgtps (int id) { sgt[id].s=sgt[id<<1].s+sgt[id<<1|1].s; sgt[id].lmxs=max(sgt[id<<1].lmxs,sgt[id<<1].s+sgt[id<<1|1].lmxs); sgt[id].rmxs=max(sgt[id<<1|1].rmxs,sgt[id<<1|1].s+sgt[id<<1].rmxs); sgt[id].mxs=max(max(max(sgt[id].lmxs,sgt[id].rmxs),sgt[id<<1].rmxs+sgt[id<<1|1].lmxs),max(sgt[id<<1].mxs,sgt[id<<1|1].mxs)); } void sgtbd (int l,int r,int id) { sgt[id].l=l,sgt[id].r=r; if (l==r) {sgt[id].lmxs=sgt[id].rmxs=sgt[id].mxs=sgt[id].s=da[l];return;} sgtbd(l,(l+r)>>1,id<<1),sgtbd(((l+r)>>1)+1,r,id<<1|1); sgtps(id); } void sgtad (int p,int val,int id) { if (sgt[id].l>p||sgt[id].r<p) return; if (sgt[id].l==p&&sgt[id].r==p) {sgt[id].s=sgt[id].lmxs=sgt[id].rmxs=sgt[id].mxs=val;return;} if (p<=((sgt[id].l+sgt[id].r)>>1)) sgtad(p,val,id<<1); else if (p>((sgt[id].l+sgt[id].r)>>1)) sgtad(p,val,id<<1|1); sgtps(id); } SGT sgtqymxs (int l,int r,int id) { SGT qy; if (sgt[id].l>r||sgt[id].r<l) return qy; if (sgt[id].l==l&&sgt[id].r==r) return sgt[id]; if (r<=((sgt[id].l+sgt[id].r)>>1)) return sgtqymxs(l,r,id<<1); else if (l>((sgt[id].l+sgt[id].r)>>1)) return sgtqymxs(l,r,id<<1|1); else { SGT lqy=sgtqymxs(l,(sgt[id].l+sgt[id].r)>>1,id<<1); SGT rqy=sgtqymxs(((sgt[id].l+sgt[id].r)>>1)+1,r,id<<1|1); qy.s=lqy.s+rqy.s; qy.lmxs=max(lqy.lmxs,lqy.s+rqy.lmxs); qy.rmxs=max(rqy.rmxs,rqy.s+lqy.rmxs); qy.mxs=max(max(max(qy.lmxs,qy.rmxs),lqy.rmxs+rqy.lmxs),max(lqy.mxs,rqy.mxs)); return qy; } sgtps(id); } int main () { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>da[i]; sgtbd(1,n,1); for(int i=1;i<=m;i++) { int opt; cin>>opt; switch(opt) { case 1: int st,ed; cin>>st>>ed;if (st>ed) swap(st,ed); cout<<sgtqymxs(st,ed,1).mxs<<endl; break; case 2: int p,s; cin>>p>>s; sgtad(p,s,1); break; } } return 0; } -
0
wocao，加了个输入挂才A了
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}const int N = 500000 + 5;
int n, m, a[N], lm[N << 2], rm[N << 2], mx[N << 2], sum[N << 2];
inline void push_up(int u) {
sum[u] = sum[u << 1] + sum[u << 1 | 1];
lm[u] = max(lm[u << 1], sum[u << 1] + lm[u << 1 | 1]);
rm[u] = max(rm[u << 1 | 1], rm[u << 1] + sum[u << 1 | 1]);
mx[u] = max(max(mx[u << 1], mx[u << 1 | 1]), rm[u << 1] + lm[u << 1 | 1]);
}void build(int rt, int l, int r) {
if (l == r) {
lm[rt] = rm[rt] = mx[rt] = sum[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
push_up(rt);
}int k, p, s;
void change(int rt, int l, int r) {
if (l == r) {
lm[rt] = rm[rt] = mx[rt] = sum[rt] = s;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) change(rt << 1, l, mid);
else if (p > mid) change(rt << 1 | 1, mid + 1, r);
push_up(rt);
}struct Data {
int klm, krm, kmx, ksum;
Data() {}
Data(int u) { klm = lm[u], krm = rm[u], kmx = mx[u], ksum = sum[u]; }
};Data query(int rt, int l, int r) {
if (p <= l && s >= r) return Data(rt);
int mid = (l + r) >> 1;
if (s <= mid) return query(rt << 1, l, mid);
else if (p > mid) return query(rt << 1 | 1, mid + 1, r);
else {
Data res;
Data d1 = query(rt << 1, l, mid);
Data d2 = query(rt << 1 | 1, mid + 1, r);
res.kmx = max(max(d1.kmx, d2.kmx), d1.krm + d2.klm);
res.klm = max(d1.klm, d1.ksum + d2.klm);
res.krm = max(d2.krm, d2.ksum + d1.krm);
res.ksum = d1.ksum + d2.ksum;
return res;
}
}int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
for (int i = 1; i <= m; i++) {
k = read(), p = read(), s = read();
if (k == 1) {
if (p > s) swap(p, s);
printf("%d\n", query(1, 1, n).kmx);
} else if (k == 2) change(1, 1, n);
}
return 0;
} -
0
测试数据 #0: Accepted, time = 15 ms, mem = 31876 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 31872 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 31872 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 31872 KiB, score = 10
测试数据 #4: Accepted, time = 171 ms, mem = 31876 KiB, score = 10
测试数据 #5: Accepted, time = 359 ms, mem = 31872 KiB, score = 10
测试数据 #6: Accepted, time = 375 ms, mem = 31872 KiB, score = 10
测试数据 #7: Accepted, time = 312 ms, mem = 31872 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 31872 KiB, score = 10
测试数据 #9: Accepted, time = 343 ms, mem = 31876 KiB, score = 10
-
0
1048922798 LV 8 @ 2016-10-17 17:02:21
调试了一下午。。。看神犇的代码看不懂。。。一气之下自己按照自己的思路写，然后居然A了。。
主要是熟练线段树的维护操作。不要对线段树的操作太僵硬。。
c++
思路的话下面的牛牛已经说了，贴一下查询和更新操作
Node Query(int u,int left,int right){
if(left<=node[u].l&&node[u].r<=right)
return node[u];
int mid=(node[u].l+node[u].r)>>1;
Node a,b,c;
if(left>mid) return Query(R(u),left,right);
else if(right<=mid) return Query(L(u),left,right);
else {
a=Query(L(u),left,mid);
b=Query(R(u),mid+1,right);
c.sum=a.sum+b.sum;
c.sumr=max(b.sumr,b.sum+a.sumr);
c.suml=max(a.suml,a.sum+b.suml);
c.subsum=max(a.subsum,b.subsum);
c.subsum=max(c.subsum,a.sumr+b.suml);
return c;
Pushup(u);
}
}
void Pushup(int u){
node[u].sum=node[L(u)].sum+node[R(u)].sum;
node[u].sumr=max(node[R(u)].sumr,node[R(u)].sum+node[L(u)].sumr);
node[u].suml=max(node[L(u)].suml,node[L(u)].sum+node[R(u)].suml);
node[u].subsum=max(node[L(u)].subsum,node[R(u)].subsum);
node[u].subsum=max(node[u].subsum,node[L(u)].sumr+node[R(u)].suml);
}
-
0
好像没有pascal啊……这年代都成珍稀动物了……
```
program V1083;
const
maxn=2000000;
emp=-233333;
type
outdata=record
ml,mr,sum,maxs:longint;
end;var
n,m,k,i,t,p,s,a,b,ans:longint;
data,l,r,ml,mr,sum,maxs:array[1..2*maxn] of longint;function max(a,b:Longint):longint;
begin
if a>b then exit(a) else exit(b);
end;procedure maintain(v:longint);
begin
ml[v]:=max(ml[l[v]],sum[l[v]]+ml[r[v]]);
mr[v]:=max(mr[r[v]],sum[r[v]]+mr[l[v]]);
sum[v]:=sum[l[v]]+sum[r[v]];
maxs[v]:=max(max(maxs[l[v]],maxs[r[v]]),mr[l[v]]+ml[r[v]]);
end;procedure built(v,x,y:longint);
var mid:Longint;
begin
if x=y then begin
sum[v]:=data[x];
ml[v]:=data[x];
mr[v]:=ml[v];
maxs[v]:=ml[v];
exit;
end;
mid:=(x+y) shr 1;
l[v]:=v*2;
r[v]:=v*2+1;
built(v*2,x,mid);
built(v*2+1,mid+1,y);
maintain(v);
end;procedure updata(v,x,y,p,s:longint);
var mid:longint;
begin
if x=y then begin
sum[v]:=s;
ml[v]:=s;
mr[v]:=ml[v];
maxs[v]:=ml[v];
exit;
end;
mid:=(x+y) shr 1;
if p<=mid then updata(v*2,x,mid,p,s);
if p>mid then updata(v*2+1,mid+1,y,p,s);
maintain(v);
end;function Query(v,x,y,a,b:longint):outdata;
var
mid:Longint;
AnsL,AnsR:outdata;
begin
if (a<=x) and (y<=b) then begin
Query.ml:=ml[v];
Query.mr:=mr[v];
Query.sum:=sum[v];
Query.maxs:=maxs[v];
exit;
end;
mid:=(x+y) shr 1;
if a<=mid then AnsL:=Query(v*2,x,mid,a,b) else AnsL.sum:=emp;
if mid<b then AnsR:=Query(v*2+1,mid+1,y,a,b) else AnsR.sum:=emp;
if AnsL.sum=emp then exit(AnsR);
if AnsR.sum=emp then exit(AnsL);
Query.ml:=max(AnsL.ml,AnsL.sum+AnsR.ml);
Query.mr:=max(AnsR.mr,AnsR.sum+AnsL.mr);
Query.sum:=AnsL.sum+AnsR.sum;
Query.maxs:=max(max(AnsL.maxs,AnsR.maxs),AnsL.mr+AnsR.ml);
end;begin
readln(n,m);
for i:=1 to n do read(data[i]);
built(1,1,n);
for i:=1 to m do begin
read(k);
if k=1 then begin
readln(a,b);
if a>b then begin
t:=a;a:=b;b:=t;
end;
ans:=Query(1,1,n,a,b).maxs;
writeln(ans);
end
else begin
readln(p,s);
updata(1,1,n,p,s);
end;
end;
end.
``` -
0
williamking5 LV 8 @ 2016-05-15 00:56:30
测试数据 #0: Accepted, time = 62 ms, mem = 71000 KiB, score = 10
测试数据 #1: Accepted, time = 78 ms, mem = 71000 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 71008 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 71004 KiB, score = 10
测试数据 #4: Accepted, time = 234 ms, mem = 71004 KiB, score = 10
测试数据 #5: Accepted, time = 312 ms, mem = 71004 KiB, score = 10
测试数据 #6: Accepted, time = 500 ms, mem = 71008 KiB, score = 10
测试数据 #7: Accepted, time = 421 ms, mem = 71008 KiB, score = 10
测试数据 #8: Accepted, time = 406 ms, mem = 71008 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 71004 KiB, score = 10
Accepted, time = 2652 ms, mem = 71008 KiB, score = 100 -
0
简单线段树 维护区间和 前缀和 后缀和 字段和即可
好像还比较快
测试数据 #0: Accepted, time = 0 ms, mem = 29912 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 29908 KiB, score = 10
测试数据 #2: Accepted, time = 62 ms, mem = 29908 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 29908 KiB, score = 10
测试数据 #4: Accepted, time = 171 ms, mem = 29904 KiB, score = 10
测试数据 #5: Accepted, time = 218 ms, mem = 29908 KiB, score = 10
测试数据 #6: Accepted, time = 421 ms, mem = 29904 KiB, score = 10
测试数据 #7: Accepted, time = 359 ms, mem = 29908 KiB, score = 10
测试数据 #8: Accepted, time = 375 ms, mem = 29908 KiB, score = 10
测试数据 #9: Accepted, time = 328 ms, mem = 29908 KiB, score = 10
Accepted, time = 2011 ms, mem = 29912 KiB, score = 100 -
0
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1500000;
int n, m, _max, l, r, sum[maxn], maxsum[maxn], presum[maxn], suffsum[maxn];
int subsum[maxn], submax[maxn], subpre[maxn], subsuff[maxn];
void uptate(int o, int L, int R, int pos, int val){
if(L == R){sum[o] = maxsum[o] = presum[o] = suffsum[o] = val;}
else{
int M = L + (R-L)/2;
if(pos <= M)uptate(2*o, L, M, pos, val);
else uptate(2*o+1, M+1, R, pos, val);
sum[o] = sum[2*o]+sum[2*o+1];
maxsum[o] = max(max(maxsum[2*o], suffsum[2*o]+presum[2*o+1]), maxsum[2*o+1]);
presum[o] = max(presum[2*o],sum[2*o]+presum[2*o+1]);
suffsum[o] = max(suffsum[2*o+1], sum[2*o+1]+suffsum[2*o]);
}
}
void query(int o, int L, int R, int l, int r){
if(l <= L&&R <= r){
_max = max(_max, maxsum[o]);
subsum[o] = sum[o];
submax[o]= maxsum[o];
subpre[o] = presum[o];
subsuff[o] = suffsum[o];
}
else{
int M = L + (R-L)/2, p1 = 0, p2 = 0;
if(l <= M){query(2*o, L, M, l, r);p1 = 1;}
if(r > M){query(2*o+1, M+1, R, l, r);p2 = 1;}
if(p1&&p2){
subsum[o] = subsum[2*o]+subsum[2*o+1];
submax[o] = max(max(submax[2*o], subsuff[2*o]+subpre[2*o+1]), submax[2*o+1]);
subpre[o] = max(subpre[2*o],subsum[2*o]+subpre[2*o+1]);
subsuff[o] = max(subsuff[2*o+1], subsum[2*o+1]+subsuff[2*o]);
_max = max(_max, submax[o]);
}
else if(p1&&!p2){
subsum[o] = subsum[2*o];
submax[o] = submax[2*o];
subpre[o] = subpre[2*o];
subsuff[o] = subsuff[2*o];
}
else if(!p1&&p2){
subsum[o] = subsum[2*o+1];
submax[o] = submax[2*o+1];
subpre[o] = subpre[2*o+1];
subsuff[o] = subsuff[2*o+1];
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
uptate(1, 1, n, i, x);
}
while(m--){
int Q;
scanf("%d %d %d", &Q, &l, &r);
if(Q == 1){
_max = -(1<<30);
query(1, 1, n, min(l, r), max(l, r));
printf("%d\n", _max);
}
else uptate(1, 1, n, l, r);
}
return 0;
}
终于。。。。。。终于。。。。。。写出来了！！！！！ -
0
wang_yanheng LV 10 @ 2016-02-01 14:01:56
回溯时维护一段区间的以下域：
+ sumL：从左端点起连续区间的最大和
+ sumR：从右端点起连续区间的最大和
+ sum：整段区间的和
+ subSum：最大子区间和以上域在叶子节点中的值，都等于节点代表公园的评分
设当前节点为 x，左孩子为 l，右孩子为 r。则：x.sumL = MAX(l.sumL, l.sum + r.sumL);
x.sumR = MAX(r.sumR, r.sum + l.sumR);
x.sum = l.sum + r.sum;
x.subSum = MAX(l.subSum, r.subSum, l.sumR + r.sumL);正确性证明略过。
查询时也差不多。要返回一个结构体（类型同树节点，其中 l 代表左端点，r 代表右端点，lc 代表左孩子，rc 代表右孩子）。以下是查询的伪代码：getSubSum(root, left, right)
IF root.l > right OR root.r < left
return NIL
ELSE IF root.l >= left AND segTree[root].r <= right
return root
ELSE
lc = getSubSum(root.lc, left, right);
rc = getSubSum(root.rc, left, right);
IF lc == NIL OR rc == NIL
IF lc != NIL
return lc
ELSE IF rc != NIL
return rc
ELSE
return NIL
ret.sumL = MAX(lc.sumL, l.sum + rc.sumL)
ret.sumR = MAX(rc.sumR, r.sum + lc.sumR)
ret.sum = lc.sum + rc.sum
ret.subSum = MAX(lc.subSum, rc.subSum, lc.sumR + rc.sumL)
return ret -
0
编译成功
测试数据 #0: Accepted, time = 31 ms, mem = 31584 KiB, score = 10
测试数据 #1: Accepted, time = 46 ms, mem = 31584 KiB, score = 10
测试数据 #2: Accepted, time = 124 ms, mem = 31588 KiB, score = 10
测试数据 #3: Accepted, time = 78 ms, mem = 31584 KiB, score = 10
测试数据 #4: Accepted, time = 327 ms, mem = 31584 KiB, score = 10
测试数据 #5: Accepted, time = 421 ms, mem = 31584 KiB, score = 10
测试数据 #6: Accepted, time = 483 ms, mem = 31584 KiB, score = 10
测试数据 #7: Accepted, time = 436 ms, mem = 31588 KiB, score = 10
测试数据 #8: Accepted, time = 483 ms, mem = 31584 KiB, score = 10
测试数据 #9: Accepted, time = 530 ms, mem = 31588 KiB, score = 10
Accepted, time = 2959 ms, mem = 31588 KiB, score = 100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 500000 + 24;
const int M = 1000 + 24;
inline int LC(int x){ return x << 1;}
inline int RC(int x){ return x << 1 | 1;}
int n,m,t,k,Case = 1;
struct node
{
int sum,l,r,all;
node()
{
sum = l = r = -0x3f3f3f;
all = 0;
}
}sum[N << 2];
void Uppush(int x)
{
sum[x].all = sum[LC(x)].all + sum[RC(x)].all;
sum[x].sum = max(sum[LC(x)].sum,sum[RC(x)].sum);
sum[x].sum = max(sum[x].sum,sum[RC(x)].l + sum[LC(x)].r);
sum[x].l = max(sum[LC(x)].l,sum[LC(x)].all + sum[RC(x)].l);
sum[x].r = max(sum[RC(x)].r,sum[RC(x)].all + sum[LC(x)].r);
}
void Buile(int x, int l, int r)
{
if(l == r)
{
scanf("%d",&sum[x].all);
sum[x].l = sum[x].r = sum[x].sum = sum[x].all;
return;
}
int mid = (l + r) >> 1;
Buile(LC(x),l, mid);
Buile(RC(x),mid + 1, r);
Uppush(x);
}
void Update(int x,int l, int r,int u, int v)
{
if(l == r)
{
sum[x].l = sum[x].r = sum[x].sum = sum[x].all = v;
return;
}
int mid = (l + r) >> 1;
if(u <= mid)
Update(LC(x),l,mid,u,v);
else
Update(RC(x),mid+1,r,u,v);
Uppush(x);
}
node Reach(int x,int l,int r,int st,int ed)
{
//printf("l = %d r = %d\n",l,r);
if(st <= l && r <= ed)
{
return sum[x];
}
int mid = (l + r) >> 1;
node a,b,c;
if(st <= mid)
a = Reach(LC(x),l,mid,st,ed);
if(mid < ed)
b = Reach(RC(x),mid+1,r,st,ed);
//printf("a = %d %d %d %d\n",a.all,a.sum,a.l,a.r);
//printf("b = %d %d %d %d\n",b.all,b.sum,b.l,b.r);
c.all = a.all + b.all;
c.sum = max(a.sum,b.sum);
c.sum = max(c.sum,b.l + a.r);
c.l = max(a.l,a.all + b.l);
c.r = max(b.r,b.all + a.r);
return c;
}
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d%d",&n,&m))
{
Buile(1,1,n);
for(int i = 0; i < m; i++)
{
scanf("%d",&k);
int a,b;
if(k == 1)
{
scanf("%d%d",&a,&b);
if(a > b)
swap(a,b);
printf("%d\n",Reach(1,1,n,a,b).sum);
}
else if(k == 2)
{
scanf("%d%d",&a,&b);
Update(1,1,n,a,b);
}
}
}
} -
0
visit_world LV 8 @ 2015-08-10 17:30:22
蒟蒻一下午就写了这一道题......
#include<cstdio>
#include<cstring>
#define inf 0x3F3F3F3F
#define maxn 524300int n,m,a[maxn],tot=0;
struct Tree {
int l, r, max, lmax, rmax, sum;
}node[maxn*2];inline int max(int a, int b) { return a>b?a:b; }
inline int min(int a,int b) { return a<b?a:b; }
inline int read() {
int f=1,x=0; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}inline void update(int root) {
node[root].sum=node[root<<1].sum+node[root<<1^1].sum;
node[root].lmax=max(node[root<<1].lmax, node[root<<1].sum+node[root<<1^1].lmax);
node[root].rmax=max(node[root<<1^1].rmax, node[root<<1^1].sum+node[root<<1].rmax);
node[root].max=max(node[root<<1].max, node[root<<1^1].max);
node[root].max=max( node[root].max, node[root<<1].rmax+node[root<<1^1].lmax);
}void build(int l, int r, int root) {
node[root].l=l, node[root].r=r;
if(l==r) {
a[++tot]=root;
node[root].sum=node[root].lmax=node[root].rmax=node[root].max=read();
return ;
}
int mid= (l+r) >> 1;
build(l, mid, root<<1), build(mid+1, r, root<<1^1);
update(root);
}void change(int pos , int v) {
node[pos].sum=node[pos].lmax=node[pos].rmax=node[pos].max=v;
while( pos >>= 1)
update(pos);
}int qright(int l, int root) {
while(node[root].l<l) root=root<<1^1;
if(node[root].l==l) return node[root].rmax;
else return max(node[root].rmax, qright(l, root^1)+node[root].sum);
}
int qleft(int r, int root) {
while(node[root].r>r) root<<=1;
if(node[root].r==r) return node[root].lmax ;
else return max(node[root].lmax, qleft(r, root^1)+node[root].sum);
}int query(int l, int r, int root) {
if(node[root].l==l&&node[root].r==r) return node[root].max;
int mid=(node[root].l+node[root].r) >>1 ;
if(mid>=r) return query( l, r, root<<1 );
else if(mid<l) return query( l, r, root<<1^1);
else {
int tmax=max(query( l, mid, root<<1), query( mid+1, r, root<<1^1) );
tmax=max(tmax, qleft( r, root<<1^1) + qright( l, root<<1));
return tmax;
}
}int main() {
n=read(), m=read();
build(1,n,1); int l, r ;
while(m--) {
switch(read()) {
case 1: l=read(), r=read();
printf("%d\n",query( min(l,r), max(l,r), 1)); break;
case 2: l=read(), r=read();
change(a[l],r); break;
default: break;
}
}
return 0;
} -
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define pi acos(-1.0)
#define LL long long
#define inf 0x7fffffffusing namespace std;
struct segment{
int l,r,s1,s2,s3,sum;
}t[2100100];
int a[1000100];
int x,y,z,n,m,op;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void update(int i)
{
/*
sum[i]=sum[i<<1]+sum[i<<1|1];
s1[i]=max(s1[i<<1],sum[i<<1]+s1[i<<1|1]);
s2[i]=max(s2[i<<1|1],sum[i<<1|1]+s2[i<<1]);
s3[i]=max(s2[i<<1]+s1[i<<1|1],max(s3[i<<1],s3[i<<1|1]));
s3[i]=max(s3[i],max(s1[i],s2[i]));
*/
t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
t[i].s1=max(t[i<<1].s1,t[i<<1].sum+t[i<<1|1].s1);
t[i].s2=max(t[i<<1|1].s2,t[i<<1|1].sum+t[i<<1].s2);
t[i].s3=max(max(t[i].s1,t[i].s2),max(t[i<<1].s3,t[i<<1|1].s3));
t[i].s3=max(t[i].s3,t[i<<1].s2+t[i<<1|1].s1);
}
void build(int i,int l,int r)
{
int mid;
t[i].l=l; t[i].r=r;
if (l==r) { t[i].s1=t[i].s2=t[i].s3=t[i].sum=a[l];
return; }
else
{
mid=(l+r)>>1;
build(i<<1,l,mid); build(i<<1|1,mid+1,r);
update(i);
}
}
void modify(int i,int x,int d)
{
int mid;
if (t[i].l==t[i].r)
{
t[i].s1=t[i].s2=t[i].s3=t[i].sum=d;
return;
}
else
{
mid=(t[i].l+t[i].r)>>1;
if (x<=mid) modify(i<<1,x,d);
else modify(i<<1|1,x,d);
update(i);
}
}
segment query(int i,int l,int r)
{
int mid;
if (t[i].l>=l && t[i].r<=r)
{
return t[i];
}
else
{
segment ans,tmp1,tmp2;
mid=(t[i].l+t[i].r)>>1;
/*if (l<=mid) tmp1=query(i<<1,l,r);
if (mid<r) tmp2=query(i<<1|1,l,r); */
if (l>mid) return query(i<<1|1,l,r);
else if (r<=mid) return query(i<<1,l,r);
else
{
tmp1=query(i<<1,l,r); tmp2=query(i<<1|1,l,r);
ans.sum=tmp1.sum+tmp2.sum;
ans.s3=max(max(tmp1.s3,tmp2.s3),tmp1.s2+tmp2.s1);
ans.s1=max(tmp1.s1,tmp1.sum+tmp2.s1);
ans.s2=max(tmp2.s2,tmp2.sum+tmp1.s2);
return ans;
}
}
}
int main()
{
n=read(); m=read();
int N=1<<(int)ceil(log(n)/log(2));
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
a[i]=read();
build(1,1,N);
while (m--)
{
op=read(); x=read(); y=read();
if (op==1)
printf("%d\n",query(1,x,y).s3);
else
modify(1,x,y);
}
return 0;
}
跪求为何一直RE
mangoyang
LV 8
@ 2017-07-12 18:33:21
信息
- ID
- 1083
- 难度
- 7
- 分类
- 数据结构 | 线段树 点击显示
- 标签
- (无)
- 递交数
- 5011
- 已通过
- 977
- 通过率
- 19%
- 被复制
- 6
- 上传者
-
Vivian Snow
