Mn Zn 求助 线段树题 卡常

P4513 小白逛公园

songhongyi @ 2020-10-07 15:59:36

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 <cstdio>
#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 = 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 = 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 )
{
    // cerr << x->l << " " << x->r << endl;
    if ( x->l == l && x->r == r )
    {
        return *x;
    }
    if ( x->l == x->r )
    {
        return *x;
    }
    int mid = ( x->l + x->r ) / 2;
    if ( r <= mid )
    {
        return query( x->lson, l, r );
    }
    if ( l > mid )
    {
        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;
}
inline int read()
{
    char c = getchar();
    int x = 0, f = 1;
    while ( c < '0' || c > '9' )
    {
        if ( c == '-' )
            f = -1;
        c = getchar();
    }
    while ( c >= '0' && c <= '9' )
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for ( int i = 1; i <= n; i++ )
    {
        a[ i ] = read();
    }
    root = new Node;
    root->l = 1, root->r = n;
    build( root );
    for ( int i = 1; i <= m; i++ )
    {
        int opt;
        opt = read();
        if ( opt == 1 )
        {
            int a, b;
            a = read(), b = read();
            if ( a > b )
            {
                swap( a, b );
            }
            printf( "%d\n", query( root, a, b ).mids );
        }
        else
        {
            int p, s;
            p = read(), s = read();
            a[ p ] = s;
            change( root, p );
        }
    }
}

4,#6~#11 TLE.


by 传奇666666 @ 2020-10-07 16:13:10

指针好评(不卡你卡谁)


by Krystallos @ 2020-10-07 16:21:05

不动态开点为啥写指针。。。


by songhongyi @ 2020-10-07 16:59:30

@传奇666666 谢谢您的帮助


|