105 条题解
-
10
mangoyang LV 8 @ 7 年前
因为要维护区间最大连续子段和，我们可以考虑用线段树维护
分析得出，一个区间的最大子段和等于MAX(左儿子(以下用lson)的最大子段和,右儿子(以下用rson)的最大子段和,左右儿子合并时的中间一段的最大子段和)
前两个项很好维护，但要注意的是中间的子段和..
观察发现，中间的子段和==以lson的右边界为端点向左扫的最大子段和+rson的左边界为端点向右扫的最大子段和；所以只需要在维护最大子段和的同时，维护以左右端点为起点的两个方向的最大子段和
实际上这两个最大字段和又等于(以lson为例，rson同理)MAX(lson的最大向左子段和,lson的总和+以rson左端点向右推的最大子段和)
再维护一个sum就可以解决这一问题，本蒟蒻太弱了，所以打的特别慢，膜拜各位大佬 -
3
正在加载...99% LV 8 @ 8 年前
JRX2015U43：
-
1
Sky1231 (sky1231) LV 10 @ 4 年前
-
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
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 @ 8 年前
调试了一下午。。。看神犇的代码看不懂。。。一气之下自己按照自己的思路写，然后居然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 @ 8 年前
测试数据 #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 @ 9 年前
回溯时维护一段区间的以下域：
+ 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 @ 9 年前
蒟蒻一下午就写了这一道题......
#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
@ 7 年前
信息
- ID
- 1083
- 难度
- 7
- 分类
- 数据结构 | 线段树 点击显示
- 标签
- (无)
- 递交数
- 5020
- 已通过
- 985
- 通过率
- 20%
- 被复制
- 6
- 上传者
-
Vivian Snow
