翰空之眼 @ 2019-06-02 10:37:32
/*
动态维护最大字段和：
1.此段的和（tr[now*2].sum + tr[now*2+1].sum）
2.包含左端单的此段最大字段和 max(tr[now*2].sum + tr[now*2+1].lm, tr[now*2].lm)
3.包含右端点的此段最大字段和 max(tr[now*2].rm + tr[now*2+1].sum, tr[now*2+1].rm)
4.此段最大字段和 max(max(tr[now*2].rm + tr[now*2+1].lm, tr[now*2].mx), tr[now*2+1].mx)
*/
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
const int N = 5e5 + 9;
struct tree{
int sum, lm, rm, mx, l, r;
}tr[N << 2], lans, rans, ans;
int a[N], n, m;
void together(int now){
tr[now].sum = tr[now*2].sum + tr[now*2+1].sum;
tr[now].lm = max(tr[now*2].sum + tr[now*2+1].lm, tr[now*2].lm);
tr[now].rm = max(tr[now*2].rm + tr[now*2+1].sum, tr[now*2+1].rm);
tr[now].mx = max(max(tr[now*2].rm + tr[now*2+1].lm, tr[now*2].mx), tr[now*2+1].mx);
}
void build(int now, int l, int r){
tr[now].l = l, tr[now].r = r;
if(l == r){
tr[now].sum = tr[now].lm = tr[now].rm = tr[now].mx = a[l];
return;
}
int mid = (l + r) / 2;
build(2*now, l, mid); build(2*now+1, mid+1, r);
together(now);
}
tree query(int now, int l, int r){
int lx = tr[now].l, rx = tr[now].r;
int mid = tr[2*now].r;
if(lx == l && rx == r) return tr[now];
if(r <= mid) return query(now*2, l, r);
if(l > mid) return query(now*2+1, l, r);
lans = query(now*2, l, mid), rans = query(now*2+1, mid+1, r);
ans.sum = lans.sum + rans.sum;
ans.lm = max(lans.sum + rans.lm, lans.lm);
ans.rm = max(lans.rm + rans.sum, rans.rm);
ans.mx = max(max(lans.rm + rans.lm, lans.mx), rans.mx);
return ans;
}
void change(int now, int p, int d){
int lx = tr[now].l, rx = tr[now].r;
if(lx == rx){
tr[now].sum = tr[now].lm = tr[now].rm = tr[now].mx = d;
return;
}
int mid = tr[2*now].r;
change(now * 2 + (mid < p), p, d);
together(now);
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
for(int i = 1; i <= m; i++){
int x, y, z; scanf("%d %d %d", &z, &x, &y);
if(z == 1) {
if(x > y) swap(x, y);
printf("%d\n", query(1, x, y).mx);
}
else change(1, x, y);
}
return 0;
}求大佬神仙们帮忙看看
by 翰空之眼 @ 2019-06-09 19:42:37
终于过了。。。
by YOU法克 @ 2019-07-23 17:28:53
@翰空之眼
dalao
我被卡到了九分 怎么办呀QAQ
by YOU法克 @ 2019-07-23 17:29:53
@翰空之眼
能不能稍微给我看一看 [照片]
by 翰空之眼 @ 2019-07-23 18:15:08
@YOU法克 我把我的代码给你看看吧？我是错在递归变量开成全局的了（一定要开在函数里！）
by 翰空之眼 @ 2019-07-23 18:15:55
/*
动态维护最大字段和：
1.此段的和（tr[now*2].sum + tr[now*2+1].sum）
2.包含左端单的此段最大字段和 max(tr[now*2].sum + tr[now*2+1].lm, tr[now*2].lm)
3.包含右端点的此段最大字段和 max(tr[now*2].rm + tr[now*2+1].sum, tr[now*2+1].rm)
4.此段最大字段和 max(max(tr[now*2].rm + tr[now*2+1].lm, tr[now*2].mx), tr[now*2+1].mx)
*/
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <cassert>
using namespace std;
const int N = 5e5 + 9;
struct tree{
int sum, lm, rm, mx, l, r;
}tr[N << 3];
int a[N], n, m;
void together(int now){
tr[now].sum = tr[now*2].sum + tr[now*2+1].sum;
tr[now].lm = max(tr[now*2].sum + tr[now*2+1].lm, tr[now*2].lm);
tr[now].rm = max(tr[now*2].rm + tr[now*2+1].sum, tr[now*2+1].rm);
tr[now].mx = max(max(tr[now*2].rm + tr[now*2+1].lm, tr[now*2].mx), tr[now*2+1].mx);
}
void build(int now, int l, int r){
tr[now].l = l, tr[now].r = r;
if(l == r){
tr[now].sum = tr[now].lm = tr[now].rm = tr[now].mx = a[l];
return;
}
int mid = (l + r) / 2;
build(2*now, l, mid); build(2*now+1, mid+1, r);
together(now);
}
tree query(int now, int l, int r){
int lx = tr[now].l, rx = tr[now].r;
int mid = tr[2*now].r;
if(l <= lx && rx <= r) return tr[now];
if(r <= mid) return query(now*2, l, r);
if(l > mid) return query(now*2+1, l, r);
tree lans = query(now*2, l, mid), rans = query(now*2+1, mid+1, r), ans;
ans.sum = lans.sum + rans.sum;
ans.lm = max(lans.sum + rans.lm, lans.lm);
ans.rm = max(lans.rm + rans.sum, rans.rm);
ans.mx = max(max(lans.rm + rans.lm, lans.mx), rans.mx);
return ans;
}
void change(int now, int p, int d){
int lx = tr[now].l, rx = tr[now].r;
assert(lx <= p && p <= rx);
if(lx == rx){
tr[now].sum = tr[now].lm = tr[now].rm = tr[now].mx = d;
return;
}
int mid = tr[2*now].r;
change(now * 2 + (mid < p), p, d);
together(now);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
for(int i = 1; i <= m; i++){
int x, y, z; scanf("%d%d%d", &z, &x, &y);
if(z == 1) {
if(x > y) swap(x, y);
printf("%d\n", query(1, x, y).mx);
}
else change(1, x, y);
}
return 0;
}by YOU法克 @ 2019-07-23 19:22:47
@翰空之眼
我自己过了，谢谢dalao
同样感谢 Orz