Mn Zn 求助线段树题

P4513 小白逛公园

songhongyi @ 2020-10-06 16:16:41

Rt,代码如下


// Problem : P4513 小白逛公园
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P4513
// Memory Limit : 128 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
using namespace std;
struct Node
{
    int l, r;  // 左右区间 [l,r]
    int sum, mids, ls,
        rs;  //区间和,区间最大子段和,包含左右端点的最大子段和
    Node *lson, *rson;
};
int a[ 500010 ];
Node* root;
void update( Node* x )
{
    // update( x->lson );
    // update( x->rson );
    x->sum = x->lson->sum + x->rson->sum;
    x->mids =
        max( x->lson->mids, max( x->rson->mids, x->lson->rs + x->rson->ls ) );
    x->ls = max( x->lson->ls, x->lson->sum + x->rson->ls );
    x->rs = max( x->rson->rs, x->rson->sum + x->lson->rs );
}
void build( Node* x )
{
    if ( x->l == x->r )
    {
        x->sum = a[ x->l ];
        x->mids = x->ls = x->rs = max( 0, x->sum );
        return;
    }
    x->lson = new Node;
    x->rson = new Node;
    int mid = ( x->l + x->r ) / 2;
    x->lson->l = x->l;
    x->lson->r = mid;
    x->rson->l = mid + 1;
    x->rson->r = x->r;
    x->lson->mids = x->lson->ls = x->lson->rs = -0x7f7f7f7f;
    x->rson->mids = x->rson->ls = x->rson->rs = -0x7f7f7f7f;
    build( x->lson );
    build( x->rson );
    update( x );
}
void change( Node* x, int p )
{
    if ( x->l == x->r && x->l == p )
    {
        x->sum = a[ p ];
        x->mids = x->ls = x->rs = max( 0, x->sum );
        return;
    }
    int mid = ( x->l + x->r ) / 2;
    if ( p <= mid )
    {
        change( x->lson, p );
    }
    else
    {
        change( x->rson, p );
    }
    update( x );
}
Node query( Node* x, int l, int r )
{
    if ( x->l == x->r )
    {
        return *x;
    }
    if ( x->r >= r )
    {
        return query( x->lson, l, r );
    }
    if ( l >= x->l )
    {
        return query( x->rson, l, r );
    }
    Node lq = query( x->lson, l, r ), rq = query( x->rson, l, r );
    Node res;
    res.sum = lq.sum + rq.sum;
    res.ls = max( lq.ls, lq.sum + rq.ls );
    res.rs = max( rq.rs, rq.sum + lq.rs );
    res.mids = max( lq.mids, max( rq.mids, lq.rs + rq.ls ) );
    return res;
}
void clear( Node* x )
{
    if ( x->l == x->r )
    {
        delete x;
        return;
    }
    clear( x->lson );
    clear( x->rson );
    delete x;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for ( int i = 1; i <= n; i++ )
    {
        cin >> a[ i ];
    }
    root = new Node;
    root->l = 1, root->r = n;
    build( root );
    for ( int i = 1; i <= m; i++ )
    {
        int opt;
        cin >> opt;
        if ( opt == 1 )
        {
            int a, b;
            cin >> a >> b;
            if ( a > b )
            {
                swap( a, b );
            }
            cout << query( root, a, b ).mids << endl;
        }
        else
        {
            int p, s;
            cin >> p >> s;
            a[ p ] = s;
            change( root, p );
        }
    }
}

样例都没过,输出

2
0

求助


by F1aMiR3 @ 2020-10-06 17:03:34

指针毒瘤 >_<


by Vomedakth @ 2020-10-06 17:19:08

@songhongyi 询问应该是必须要选一段,所以你的

x->mids = x->ls = x->rs = max( 0, x->sum );

就应该改为

x->mids = x->ls = x->rs = x->sum

此外,你的询问程序我没有看懂,个人建议参考一下题解的写法,(至少我认为这样的可读性不高)


by Vomedakth @ 2020-10-06 17:30:14

顺便说一句,我们学长说,对于这种指针线段树,最好不要用new动态开点,常数巨大,建议先开一个内存池,然后放指针


by songhongyi @ 2020-10-07 14:10:26

@翊雲 只过了样例


by Vomedakth @ 2020-10-07 16:52:39

@songhongyi

此外,你的询问程序我没有看懂,个人建议参考一下题解的写法

估计你的询问程序也写挂了吧


by songhongyi @ 2020-10-07 16:57:50

@翊雲 这个做法确实是错的,能被卡到O(n)


|