jins3599 @ 2019-11-03 15:23:55
rt
#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N = 5e5 + 10;
int n , m , a[N];
struct Seg {
int l , r , len;
int lft , rgt , mid , dis;
}t[N << 2];
void pushup(int x) {
t[x].dis = t[ls(x)].dis + t[rs(x)].dis;
t[x].lft = max(t[ls(x)].lft , t[ls(x)].dis + t[rs(x)].lft);
t[x].rgt = max(t[rs(x)].rgt , t[rs(x)].dis + t[ls(x)].rgt);
t[x].mid = max(t[ls(x)].mid , t[rs(x)].mid);
t[x].mid = max(t[x].mid , t[ls(x)].rgt + t[rs(x)].lft);
}
void built(int x , int l ,int r ) {
t[x].l = l , t[x].r = r;
t[x].len = r - l + 1;
if(l == r) {
t[x].lft = t[x].rgt = t[x].mid = t[x].dis = a[l]; return;
}
int mid = (l + r )>> 1;
built(ls(x) , l , mid);
built(rs(x) , mid + 1 , r);
pushup(x);
}
Seg query(int x , int l , int r ) {
if(t[x].l >= l && t[x].r <= r) return t[x];
int mid = (t[x].l + t[x].r) >> 1;
Seg ans , lson , rson;
lson.dis = lson.mid = lson.lft = lson.rgt = -inf;
rson.dis = rson.mid = rson.lft = rson.rgt = -inf;
if(l <= mid) lson = query(ls(x) , l , r);
if(r > mid ) rson = query(rs(x) , l , r);
ans.lft = max(lson.lft , rson.lft + lson.dis);
ans.rgt = max(rson.rgt , lson.rgt + rson.dis);
ans.mid = max(lson.mid , rson.mid);
ans.mid = max(ans.mid , lson.rgt + rson.lft);
pushup(x);
return ans;
}
void updata(int x , int p , int w) {
if(t[x].l == t[x].r) {
t[x].lft = t[x].rgt = t[x].mid = t[x].dis = w; return;
}
int mid = (t[x].l + t[x].r) >> 1;
if(p <= mid) updata(ls(x) , p , w);
else updata(rs(x) , p , w);
pushup(x);
}
int main () {
//freopen("data.txt" , "r" , stdin);
//freopen("ans1.out" , "w" , stdout);
scanf("%d %d" , &n, &m);
for(int i = 1 ; i <= n ; ++ i) scanf("%d" , a + i);
built(1 ,1 ,n);
while( m --) {
int opt , l , r;
scanf("%d %d %d" , &opt , &l , &r);
if(opt == 1) {
if(l > r) swap(l , r);
Seg rans = query(1 , l , r);
printf("%d\n" , rans.mid);
} else {
updata(1 , l , r);
}
}
return 0;
}
by jins3599 @ 2019-11-03 15:30:16
@bit_ 不是对拍的程序啦,是直接下载WA的数据,在本地和答案输出是一样的,交上去就WA了
by 与我常在 @ 2019-11-03 15:40:45
@jins3599 一定是评测姬出错了(确信
by xwmwr @ 2019-11-03 15:43:54
sysrem fc?
by bit_ @ 2019-11-03 16:00:07
@jins3599 那么建议弄个题解对一下拍呢qwq
by jins3599 @ 2019-11-03 16:11:46
@水比田昭寿 是的
by jins3599 @ 2019-11-03 16:12:30
@bit_
我A了,只是把query中的赋初值改到了构造函数里面。
但是为什么?洛谷的编译环境还和本地不同?
by bit_ @ 2019-11-03 16:17:04
@jins3599 玄学问题很正常qwq我好几棵线段树思路一样代码基本一样但是好多都挂掉了qwq一般这种情况我都重构
by 一扶苏一 @ 2019-11-03 16:32:10
@jins3599 局部变量初值是随机的啊,你 lson
和 rson
在 if
不满足条件的时候是没有初值的,然后就挂了
by jins3599 @ 2019-11-03 16:44:48
@一扶苏一
我没有写if
赋初值...我是在if
上面直接赋初值的
by jins3599 @ 2019-11-03 16:45:26
lson.dis = lson.mid = lson.lft = lson.rgt = -inf;
rson.dis = rson.mid = rson.lft = rson.rgt = -inf;