@[__巴黎夜雨丶](/space/show?uid=107703) 不，比如一个区间你往上和的时候有一个会被-INF合到
by Sai0511 @ 2019-01-28 21:41:19
@[Kirito_Rivaille](/space/show?uid=54047) qwqwq
我刚来看
by 花里心爱 @ 2019-01-28 21:48:36
@[Kirito_Rivaille](/space/show?uid=54047) 好的咱来看啦~
by 星小雨 @ 2019-01-28 21:49:55
@[星小雨](/space/show?uid=20435) 感激不尽qwq
by 兮水XiShui丶 @ 2019-01-28 22:13:18
@[Kirito_Rivaille](/space/show?uid=54047) 是线段树的问题吗）
by 星小雨 @ 2019-01-28 22:34:52
@[Kirito_Rivaille](/space/show?uid=54047) 那啥...
您$\texttt{LaTeX}$使用方法好诡异的说..quq
为啥要写成`$LaTeX$`这样啊，明明只是普通英文符号文本啊... 应当写成`$\texttt{LaTeX}$`这样比较标准吧qwq
by Rbu_nas @ 2019-01-28 23:09:16
@[Sai_0511](/space/show?uid=114320) @[星小雨](/space/show?uid=20435) 现在改了一下，变成MLE了..
但是交到SP1716的那个数据弱化版就A了....
求帮忙优化一下空间
```cpp
#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 兮水XiShui丶 @ 2019-01-29 08:14:58
@[Kirito_Rivaille](/space/show?uid=54047) 空间应该是没问题的，剩下的应该是一些细节你没注意导致递归爆了或怎样。
by Sai0511 @ 2019-01-29 10:28:54
```cpp
#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 Sai0511 @ 2019-01-29 10:29:17
@[Sai_0511](/space/show?uid=114320) 哇指针选手（
by 兮水XiShui丶 @ 2019-01-29 10:30:37