随便打一打含左端点连续最大值,含右端点连续最大值,以及连续最大字段和就好了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Seg{ll ls,rs,ms,s;}t[1250005];
ll a[N];
void build(int p,int l,int r)
{
if(l==r){t[p].ls=t[p].rs=t[p].ms=t[p].s=a[l];return ;}
int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
t[p].s=t[p<<1].s+t[p<<1|1].s;
t[p].ls=max(t[p<<1].ls,t[p<<1].s+t[p<<1|1].ls);
t[p].rs=max(t[p<<1|1].rs,t[p<<1|1].s+t[p<<1].rs);
t[p].ms=max(t[p<<1].ms,max(t[p<<1|1].ms,t[p<<1].rs+t[p<<1|1].ls));
}
void change(int p,int l,int r,int x,ll d)
{
if(l==r){t[p].ls=t[p].rs=t[p].ms=t[p].s=d;return ;}
int mid=l+r>>1;
if(x<=mid)change(p<<1,l,mid,x,d);
else change(p<<1|1,mid+1,r,x,d);
t[p].s=t[p<<1].s+t[p<<1|1].s;
t[p].ls=max(t[p<<1].ls,t[p<<1].s+t[p<<1|1].ls);
t[p].rs=max(t[p<<1|1].rs,t[p<<1|1].s+t[p<<1].rs);
t[p].ms=max(t[p<<1].ms,max(t[p<<1|1].ms,t[p<<1].rs+t[p<<1|1].ls));
}
Seg query(int p,int l,int r,int ql,int qr)
{
if(ql==l&&qr==r)return t[p];
int mid=l+r>>1;
if(qr<=mid)return query(p<<1,l,mid,ql,qr);
else if(ql>mid)return query(p<<1|1,mid+1,r,ql,qr);
else
{
Seg lc,rc,now;
lc=query(p<<1,l,mid,ql,mid);
rc=query(p<<1|1,mid+1,r,mid+1,qr);
now.s=lc.s+rc.s;
now.ls=max(lc.ls,lc.s+rc.ls);
now.rs=max(rc.rs,rc.s+lc.rs);
now.ms=max(lc.ms,max(rc.ms,lc.rs+rc.ls));
return now;
}
}
int main()
{
int n,m;qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
build(1,1,n);
for(int i=1,k,l,r,x;i<=m;i++)
{
qr(k);ll d;
if(k==1){qr(l),qr(r);if(l>r)swap(l,r);qw(query(1,1,n,l,r).ms);puts("");}
else {qr(x);qr(d);change(1,1,n,x,d);}
}
return 0;
}
最后一次更新于2019-10-11
0 条评论