萌新求助,卡在 9 分咋办啊

P4513 小白逛公园

Gypsophila @ 2018-10-16 21:58:32

有人能帮我找到错误或者指出那里有问题啊,感谢万分啊

 #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 500500;
int n, m, cnt, a[MAXN];
struct node {
    int left, right, ls, rs, s, sum;
    node *ch[2];
}pool[MAXN * 2], *root;
inline void pushup(node *r) {
    r->sum = r->ch[0]->sum + r->ch[1]->sum;
    r->ls = max(r->ch[0]->ls, r->ch[0]->sum + r->ch[1]->ls);
    r->rs = max(r->ch[1]->rs, r->ch[1]->sum + r->ch[0]->rs);
    if(r->ch[0]->s < 0 && r->ch[1]->s < 0) r->s = max(r->ch[0]->s, r->ch[1]->s);
    else {
        r->s = 0;
        if(r->ch[0]->rs > 0) r->s += r->ch[0]->rs;
        if(r->ch[1]->ls > 0) r->s += r->ch[1]->ls;
    }
    r->s =  max( r->s, max(r->ch[0]->s, r->ch[1]->s) );
}
inline void build(node *r, int left, int right) {
    r->left = left, r->right = right;
    if(left == right) {
        r->s = r->sum = r->ls = r->rs = a[left];
        return ;
    }
    int mid = (left + right) / 2;
    node *lson = &pool[++cnt], *rson = &pool[++cnt];
    r->ch[0] = lson, r->ch[1] = rson;
    build(lson, left, mid), build(rson, mid + 1, right);
    pushup(r);
}
inline void update(node *r, int pos, int x) {
    if(r->left == r->right && r->left == pos) {
        r->s = r->sum = r->ls = r->rs = x;
        return ;
    }pushup(r);
    int mid = (r->left + r->right) / 2;
    if(pos <= mid) update(r->ch[0], pos, x);
    else update(r->ch[1], pos, x);
    pushup(r);
}
inline node *query(node *r, int left, int right) {
    if(r->left == left && r->right == right) return r;
    if(r->ch[0]->right >= right) return query(r->ch[0], left, right);
    else if(r->ch[1]->left <= left) return query(r->ch[1], left, right);
    else {
        node *ret = r, *ll, *rr;
        ll = query(r->ch[0], left, r->ch[0]->right);
        rr = query(r->ch[1], r->ch[1]->left, right);
        ret->ls = max(ll->ls, ll->sum + rr->ls);
        ret->rs = max(rr->rs, rr->sum + ll->rs);
        if(ll->s < 0 && rr->s < 0) ret->s = max(ll->s, rr->s);
        else {
            ret->s = 0;
            if(ll->rs > 0) ret->s += ll->rs;
            if(rr->ls > 0) ret->s += rr->ls;
        }   
        ret->s =  max( ret->s, max(ll->s, rr->s) );
        return ret;
    }
} 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(root = &pool[0], 1, n);
    for(int i = 1; i <= m; i++) {
        int opt, l, r; scanf("%d%d%d", &opt, &l, &r);
        if(opt == 1) {
            if(l > r) swap(l, r);
            printf("%d\n", query(root, l, r)->s);
        } else update(root, l, r);
    }
    return 0;
}

by xenonex @ 2018-10-16 22:01:06

@ACの666 你看题目保证了l<=r吗23333


by Gypsophila @ 2018-10-16 22:01:54

@xenonex 窝swap了啊


by xenonex @ 2018-10-16 22:02:22

@ACの666 当我没说QAQ反正我被卡了两次


by Gypsophila @ 2018-10-16 22:30:06

@xenonex 我知道了。。。合并的时候 ret 应该新建一个节点而不是复制为 r 。。。 为了这个我不知道重构了多少次代码。。。


|