上帝啊，这题输出用write不是用writeln，用write格式错误，writeln ac= =

编译通过...

测试数据1：答案正确... 0ms

测试数据2：答案正确... 0ms

测试数据3：答案正确... 134ms

测试数据4：答案正确... 56ms

测试数据5：答案正确... 775ms

测试数据6：答案正确... 1384ms

测试数据7：答案正确... 1666ms

测试数据8：答案正确... 1588ms

测试数据9：答案正确... 1728ms

测试数据10：答案正确... 1666ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：8997ms

vijos对动态内存处理得太差了。

开始作这题之前 这题总提交次数才15

AC之后 提交次数已经71了...

writeln!writeln!writeln!writeln!writeln!writeln!
a>b!a>b!a>b!a>b!a>b!a>b!a>b!
提交六次，被坑死

很裸的一道线段树，果断一次A。
编译成功

测试数据 #0: Accepted, time = 3 ms, mem = 49464 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 49460 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 49460 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 49460 KiB, score = 10
测试数据 #4: Accepted, time = 218 ms, mem = 49464 KiB, score = 10
测试数据 #5: Accepted, time = 390 ms, mem = 49460 KiB, score = 10
测试数据 #6: Accepted, time = 421 ms, mem = 49460 KiB, score = 10
测试数据 #7: Accepted, time = 437 ms, mem = 49468 KiB, score = 10
测试数据 #8: Accepted, time = 437 ms, mem = 49460 KiB, score = 10
测试数据 #9: Accepted, time = 437 ms, mem = 49460 KiB, score = 10
Accepted, time = 2482 ms, mem = 49468 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAXN 500001

struct saver {
int ls,rs,s,ms;
} s[MAXN*4];
int L[MAXN*4],R[MAXN*4];
int n,m;
int a[MAXN];

saver Merge(saver x,saver y) {
saver u;
u.s=x.s+y.s;
u.ls=max(x.ls,x.s+y.ls);
u.rs=max(y.rs,x.rs+y.s);
u.ms=max(max(x.rs+y.ls,x.ms),y.ms);
return u;
}

void Build(int l,int r,int t) {
L[t]=l,R[t]=r;
if (l==r) {
s[t].ls=s[t].rs=s[t].ms=s[t].s=a[l];
return ;
}
Build(l,(l+r)>>1,t<<1);
Build(((l+r)>>1)+1,r,(t<<1)^1);
s[t]=Merge(s[t<<1],s[(t<<1)^1]);
}

saver maxsum(int l,int r,int t) {
if (L[t]==l&&R[t]==r) return s[t];
int mid=(L[t]+R[t])>>1;
if (r<=mid) return maxsum(l,r,t<<1);
if (l>mid) return maxsum(l,r,(t<<1)^1);
return Merge(maxsum(l,mid,t<<1),maxsum(mid+1,r,(t<<1)^1));
}

void Change(int x,int y,int t) {
if (L[t]==R[t]) {
a[x]=y;
s[t].ls=s[t].rs=s[t].ms=s[t].s=a[x];
return ;
}
if (x<=((L[t]+R[t])>>1)) Change(x,y,t<<1)
; else Change(x,y,(t<<1)^1);
s[t]=Merge(s[t<<1],s[(t<<1)^1]);
}

int main() {
scanf("%d%d",&n,&m);
for (int i=0;i++<n;) scanf("%d",&a[i]);
Build(1,n,1);
while (m--) {
int k,l,r;
scanf("%d%d%d",&k,&l,&r);
if (k==1) {
if (l>r) swap(l,r);
saver ans=maxsum(l,r,1);
printf("%d\n",ans.ms);
} else {
Change(l,r,1);
}
}
return 0;
}