不知道什么原因
在ACwing上面也交过几乎相同的代码
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long A[1000010];
struct SEG
{
long long l,r;
long long lmax;
long long rmax;
long long sum;
long long date;
}s[2000010];
void build(long long p,long long l,long long r)
{
s[p].l=l;
s[p].r=r;
if(l==r)
{
s[p].lmax=s[p].rmax=s[p].sum=s[p].date=A[l];
return ;
}
long long mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
s[p].lmax=max(s[p*2].lmax,s[p*2].sum+s[p*2+1].lmax);
s[p].rmax=max(s[p*2+1].rmax,s[p*2+1].sum+s[p*2].rmax);
s[p].sum=s[p*2].sum+s[p*2+1].sum;
s[p].date=max(max(s[p*2].date,s[p*2+1].date),s[p*2+1].lmax+s[p*2].rmax);
}
void change(long long p,long long x,long long v)
{
if(s[p].l==s[p].r)
{
s[p].lmax=s[p].rmax=s[p].sum=s[p].date=v;
return ;
}
long long mid=(s[p].l+s[p].r)/2;
if(x<=mid)change(p*2,x,v);
if(mid<x)change(p*2+1,x,v);
s[p].lmax=max(s[p*2].lmax,s[p*2].sum+s[p*2+1].lmax);
s[p].rmax=max(s[p*2+1].rmax,s[p*2+1].sum+s[p*2].rmax);
s[p].sum=s[p*2].sum+s[p*2+1].sum;
s[p].date=max(max(s[p*2].date,s[p*2+1].date),s[p*2+1].lmax+s[p*2].rmax);
}
struct ELE
{
long long lmax;
long long rmax;
long long sum;
long long date;
};
ELE query(long long p,long long l,long long r)
{
if(l<=s[p].l&&s[p].r<=r)return ELE{s[p].lmax,s[p].rmax,s[p].sum,s[p].date};
long long mid=(s[p].l+s[p].r)/2;
ELE ret;
ELE retl;
ELE retr;
if(l<=mid&&r<=mid)
return query(p*2,l,r);
else if(mid<r&&mid<l)
return query(p*2+1,l,r);
else
{
retl=query(p*2,l,r);
retr=query(p*2+1,l,r);
ret.date=max(max(retl.date,retr.date),retl.rmax+retr.lmax);
ret.sum=retl.sum+retr.sum;
ret.lmax=max(retl.lmax,retl.sum+retr.lmax);
ret.rmax=max(retr.rmax,retr.sum+retl.rmax);
}
return ret;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
scanf("%lld",&A[i]);
build(1,1,n);
scanf("%lld",&m);
for(long long i=1;i<=m;i++)
{
long long o;
scanf("%lld",&o);
if(o==1)
{
long long l,r;
scanf("%lld%lld",&l,&r);
if(l>r)swap(l,r);
ELE ret=query(1,l,r);
long long ans=-0x3f3f3f3f;
ans=max(ret.date,ans);
ans=max(ret.lmax,ans);
ans=max(ret.rmax,ans);
ans=max(ret.sum,ans);
printf("%lld\n",ans);
}
else
{
long long x,v;
scanf("%lld%lld",&x,&v);
change(1,x,v);
}
}
return 0;
}
有大佬帮蒟蒻看看的嘛