萌新刚学OI求助，过了样例，几乎全WA

P4513 小白逛公园

兮水XiShui丶 @ 2019-01-28 21:00:19

RT\ qwq... 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

template < class T > 
inline void read ( T &x ) {
    int s = 0 , w = 1;
    char ch = getchar ();
    while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
    while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
    x = s * w;
    return;
}
template < typename T , typename ...Argc > 
inline void read ( T &x , Argc &...argc ) {
    read ( x );
    read ( argc... );
    return;
} 

const int INF = 998244353;
const int N = 5e5 + 10;

int n , m;              
int val[N];                 
struct Tree {
    int size;
    int lmax , rmax;
    int val , sum;
}tree[N << 2];

namespace Support {
    inline void swap ( int x , int y ) {
        int t = x;
        x = y;
        y = t;
    }
    inline int max ( int x , int y ) {
        return x > y ? x : y;
    }
    inline int min ( int x , int y ) {
        return x < y ? x : y;
    }
}

using namespace Support;

#define LC ( root << 1 )
#define RC ( root << 1 | 1 )  

void Build ( int root , int start , int end ) {
    tree[root].size = end - start + 1;
    if ( start == end ) {
        tree[root].lmax = val[start];
        tree[root].rmax = val[start];
        tree[root].val = val[start];
        tree[root].sum = val[start];
        return;
    }
    int mid = ( start + end ) >> 1;
    Build ( LC , start , mid );
    Build ( RC , mid + 1 , end );
    tree[root].sum = tree[LC].sum + tree[RC].sum;
    tree[root].lmax = max ( tree[LC].lmax , tree[RC].lmax + tree[LC].sum );
    tree[root].rmax = max ( tree[RC].rmax , tree[RC].sum + tree[LC].rmax );
    tree[root].val = max ( max ( tree[RC].val , tree[LC].val ) , tree[LC].rmax + tree[RC].lmax ); 
    return;
}              
void update ( int root , int start , int end , int pos , int val ) {
    if ( pos > end || pos < start ) 
        return; 
    if ( start == end ) {
        if ( start == pos ) {
            tree[root].val = val;
            tree[root].lmax = val;
            tree[root].rmax = val;
            tree[root].sum = val;
        }
        return;
    }
    int mid = ( start + end ) >> 1;
    update ( LC , start , mid , pos , val );
    update ( RC , mid + 1 , end , pos , val );
    tree[root].sum = tree[LC].sum + tree[RC].sum;
    tree[root].lmax = max ( tree[LC].lmax , tree[RC].lmax + tree[LC].sum );
    tree[root].rmax = max ( tree[RC].rmax , tree[RC].sum + tree[LC].rmax );
    tree[root].val = max ( max ( tree[RC].val , tree[LC].val ) , tree[LC].rmax + tree[RC].lmax ); 
    return;
}   
Tree check ( int root , int nstart , int nend , int qstart , int qend ) {
    Tree ne;
    ne.lmax = ne.rmax = ne.sum = ne.val = -INF;
    if ( qstart > nend || qend < nstart ) return ne;
    if ( qstart <= nstart && qend >= nend ) return tree[root];
    int mid = ( nstart + nend ) >> 1;
    Tree x = check ( LC , nstart , mid , qstart , qend )  , y = check ( RC , mid + 1 , nend , qstart , qend );
    ne.sum = x.sum + y.sum;
    ne.lmax = max ( x.lmax , y.lmax + x.sum );
    ne.rmax = max ( y.rmax , x.rmax + y.sum );
    ne.val = max ( max ( x.val , y.val ) , x.rmax + y.lmax );
    return ne;
}

int main ( void ) {
    read ( n , m );
    for ( int i = 1 ; i <= n ; i++ ) 
        read ( val[i] );
    Build ( 1 , 1 , n );
    for ( int i = 1 ; i <= m ; i++ ) {
        int opts;
        read ( opts );
        if ( opts == 1 ) {
            int l , r;
            read ( l , r );
            if ( l > r ) 
                swap ( l ,r );
            printf ( "%d\n" , check ( 1 , 1 , n , l , r ).val );
            continue;
        }
        else if ( opts == 2 ) {
            int p , s;
            read ( p , s );
            update ( 1 , 1 , n , p , s );
            continue;
        }
    }
    return 0;
}

by Sai0511 @ 2019-01-28 21:41:19

@__巴黎夜雨丶 不，比如一个区间你往上和的时候有一个会被-INF合到

by 花里心爱 @ 2019-01-28 21:48:36

@Kirito_Rivaille qwqwq   我刚来看

by 星小雨 @ 2019-01-28 21:49:55

@Kirito_Rivaille 好的咱来看啦~

by 兮水XiShui丶 @ 2019-01-28 22:13:18

@星小雨 感激不尽qwq

by 星小雨 @ 2019-01-28 22:34:52

@Kirito_Rivaille 是线段树的问题吗）

by Rbu_nas @ 2019-01-28 23:09:16

@Kirito_Rivaille 那啥...

您\texttt{LaTeX}使用方法好诡异的说..quq

为啥要写成$LaTeX$这样啊，明明只是普通英文符号文本啊... 应当写成$\texttt{LaTeX}$这样比较标准吧qwq

by 兮水XiShui丶 @ 2019-01-29 08:14:58

@Sai_0511 @星小雨 现在改了一下，变成MLE了..
但是交到SP1716的那个数据弱化版就A了....
求帮忙优化一下空间 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

template < class T > 
inline void read ( T &x ) {
    int s = 0 , w = 1;
    char ch = getchar ();
    while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
    while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
    x = s * w;
    return;
}
template < typename T , typename ...Argc > 
inline void read ( T &x , Argc &...argc ) {
    read ( x );
    read ( argc... );
    return;
} 

const int INF = 998244353;
const int N = 4e5 + 10;

int n , m;              
int val[N];                 
struct Tree {
    int size;
    int lmax , rmax;
    int val , sum;
}tree[N << 2];

namespace Support {
    inline void swap ( int x , int y ) {
        int t = x;
        x = y;
        y = t;
    }
    inline int max ( int x , int y ) {
        return x > y ? x : y;
    }
    inline int min ( int x , int y ) {
        return x < y ? x : y;
    }
}

using namespace Support;

#define LC ( root << 1 )
#define RC ( root << 1 | 1 )  

void Build ( int root , int start , int end ) {
    tree[root].size = end - start + 1;
    if ( start == end ) {
        tree[root].lmax = val[start];
        tree[root].rmax = val[start];
        tree[root].val = val[start];
        tree[root].sum = val[start];
        return;
    }
    int mid = ( start + end ) >> 1;
    Build ( LC , start , mid );
    Build ( RC , mid + 1 , end );
    tree[root].sum = tree[LC].sum + tree[RC].sum;
    tree[root].lmax = max ( tree[LC].lmax , tree[RC].lmax + tree[LC].sum );
    tree[root].rmax = max ( tree[RC].rmax , tree[RC].sum + tree[LC].rmax );
    tree[root].val = max ( max ( tree[RC].val , tree[LC].val ) , tree[LC].rmax + tree[RC].lmax ); 
    return;
}              
void update ( int root , int start , int end , int pos , int val ) {
    if ( pos > end || pos < start ) 
        return; 
    if ( start == end ) {
        if ( start == pos ) {
            tree[root].val = val;
            tree[root].lmax = val;
            tree[root].rmax = val;
            tree[root].sum = val;
        }
        return;
    }
    int mid = ( start + end ) >> 1;
    update ( LC , start , mid , pos , val );
    update ( RC , mid + 1 , end , pos , val );
    tree[root].sum = tree[LC].sum + tree[RC].sum;
    tree[root].lmax = max ( tree[LC].lmax , tree[RC].lmax + tree[LC].sum );
    tree[root].rmax = max ( tree[RC].rmax , tree[RC].sum + tree[LC].rmax );
    tree[root].val = max ( max ( tree[RC].val , tree[LC].val ) , tree[LC].rmax + tree[RC].lmax ); 
    return;
}   
Tree check ( int root , int nstart , int nend , int qstart , int qend ) {
    if ( qstart <= nstart && qend >= nend ) return tree[root]; 
    int mid = ( nstart + nend ) >> 1;
    if ( qend <= mid ) 
        return check ( LC , nstart , mid , qstart , qend );
    else if ( qstart > mid )
        return check ( RC , mid + 1 , nend , qstart , qend );
    else {     
        Tree ne;
        Tree x = check ( LC , nstart , mid , qstart , qend )  , y = check ( RC , mid + 1 , nend , qstart , qend );
        ne.sum = x.sum + y.sum;
        ne.lmax = max ( x.lmax , y.lmax + x.sum );
        ne.rmax = max ( y.rmax , x.rmax + y.sum );
        ne.val = max ( max ( x.val , y.val ) , x.rmax + y.lmax );
        return ne;
    }
}

int main ( void ) {
    read ( n , m );
    for ( int i = 1 ; i <= n ; i++ ) 
        read ( val[i] );
    Build ( 1 , 1 , n );
    for ( int i = 1 ; i <= m ; i++ ) {
        int opts;
        read ( opts );
        if ( opts == 1 ) {
            int l , r;
            read ( l , r );
            if ( l > r ) 
                swap ( l ,r );
            printf ( "%d\n" , check ( 1 , 1 , n , l , r ).val );
            continue;
        }
        else if ( opts == 2 ) {
            int p , s;
            read ( p , s );
            update ( 1 , 1 , n , p , s );
            continue;
        }
    }
    return 0;
}

by Sai0511 @ 2019-01-29 10:28:54

@Kirito_Rivaille 空间应该是没问题的，剩下的应该是一些细节你没注意导致递归爆了或怎样。

by Sai0511 @ 2019-01-29 10:29:17

#include <bits/stdc++.h>
#define il inline
#define gc getchar
#define isd isdigit
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define _swap(x,y) (x ^= y ^= x ^= y)
const int MAXN = 5e5 + 10;
using namespace std;
template<typename T> il void read(T& res) {
    res = 0;char c;bool sign = 0;
    for(c = gc();!isd(c);c = gc()) sign |= c == '-';
    for(;isd(c);c = gc()) res = (res << 1) + (res << 3) + (c ^ 48);
    res *= (sign) ? -1 : 1;
    return;
}
int n,m,i,j,k;        
int a[MAXN];
struct TreeNode {
    int sum,lsum,rsum,msum;
    TreeNode() {
        this -> sum = 0;
        this -> lsum = 0;
        this -> rsum = 0;
        this -> msum = 0;
    }
    TreeNode(int _sum,int _lsum,int _rsum,int _msum) {
        sum = _sum;lsum = _lsum;rsum = _rsum;msum = _msum;
    }
}tr[MAXN << 2];
il int _max(int x,int y) {
    return x > y ? x : y;
}
il int max3(int x,int y,int z) {
    int res = _max(x,y);
    res = _max(res,z);
    return res;
}
il void pushup(int num) {
    int ls = lson(num),rs = rson(num);
    tr[num].lsum = _max(tr[ls].lsum,tr[ls].sum + tr[rs].lsum);
    tr[num].rsum = _max(tr[rs].rsum,tr[rs].sum + tr[ls].rsum);
    tr[num].sum = tr[ls].sum + tr[rs].sum;
    tr[num].msum = max3(tr[ls].msum,tr[rs].msum,tr[ls].rsum + tr[rs].lsum);
    return;
}
void build(int l,int r,int num) {
    if(l == r) {
        tr[num].lsum = tr[num].rsum = tr[num].msum = tr[num].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,lson(num));
    build(mid + 1,r,rson(num));
    pushup(num);
    return;
}
void add(int idx,int l,int r,int num,int val) {
    if(l == idx && r == idx) {
        tr[num].lsum = val;
        tr[num].rsum = val;
        tr[num].msum = val;
        tr[num].sum  = val;
        return;
    }
    int mid = l + r >> 1;
    if(idx <= mid) add(idx,l,mid,lson(num),val);
    else add(idx,mid + 1,r,rson(num),val);
    pushup(num);
    return;
}
TreeNode query(int ql,int qr,int l,int r,int num) {
    if(ql <= l && r <= qr) return tr[num];
    int mid = l + r >> 1;
    if(ql <= mid) {
        if(mid < qr) {
            TreeNode trl,trr,res;
            trl = query(ql,qr,l,mid,lson(num));
            trr = query(ql,qr,mid + 1,r,rson(num));
            res.sum = trl.sum + trr.sum;
            res.lsum = _max(trl.lsum,trl.sum + trr.lsum);
            res.rsum = _max(trr.rsum,trr.sum + trl.rsum);
            res.msum = max3(trl.msum,trr.msum,trl.rsum + trr.lsum);
            return res;
        } else return query(ql,qr,l,mid,lson(num));
    } else return query(ql,qr,mid + 1,r,rson(num)); 
}
int main() {
    read(n);read(m);
    for(int i = 1;i <= n;i++) read(a[i]);
    build(1,n,1);
    for(int i =  1;i <= m;i++) {
        int opt,x,y;read(opt);read(x);read(y);
        if(opt == 1) {
            if(x > y) _swap(x,y);
            printf("%d\n",query(x,y,1,n,1).msum);
        } else add(x,1,n,1,y);
    }   
    return 0;
}

by 兮水XiShui丶 @ 2019-01-29 10:30:37

@Sai_0511 哇指针选手（

上一页 | 下一页