Sktic @ 2022-08-12 20:10:43
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long int ll;
struct node
{
ll l,r;
ll mal,mar;
ll sum;
ll ans;
}c[maxn<<2];
ll a[maxn];
void pushup(int x)
{
c[x].mal=max(c[x<<1].mal,c[x<<1].sum+c[x<<1|1].mal);
c[x].mar=max(c[x<<1|1].mar,c[x<<1|1].sum+c[x<<1].mar);
c[x].sum=c[x<<1].sum+c[x<<1|1].sum;
c[x].ans=max(max(c[x<<1].ans,c[x<<1|1].ans),c[x<<1].mar+c[x<<1|1].mal);
}
void build(int l,int r,int x)
{
if(l==r)
{
c[x].l=l,c[x].r=r;
c[x].mal=c[x].mar=c[x].ans=a[l]=c[x].sum=a[l];
return;
}
c[x].l=l;c[x].r=r;
int mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
pushup(x);
return;
}
void modify(int x,int pos,int k)
{
if(c[x].l==c[x].r)
{
c[x].sum=c[x].mal=c[x].mar=c[x].ans=k;
return;
}
ll mid=(c[x].l+c[x].r)>>1;
if(mid>=pos)
modify(x<<1,pos,k);
else
modify(x<<1|1,pos,k);
pushup(x);
return;
}
node query(int x,int l,int r)
{
if(c[x].l>=l&&c[x].r<=r)
return c[x];
ll mid=(c[x].l+c[x].r)>>1;
if(mid>=l)
return query(x<<1,l,r);
else if(mid+1<=r)
return query(x<<1|1,l,r);
node ls=query(x<<1,l,r),rs=query(x<<1|1,l,r),ans;
ans.l=c[x].l;ans.r=c[x].r;
ans.mal=max(ls.mal,ls.sum+rs.mal);
ans.mar=max(rs.mar,rs.sum+ls.mar);
ans.sum=ls.sum+rs.sum;
ans.ans=max(max(ls.ans,rs.ans),ls.mar+rs.mal);
return ans;
}
int main()
{
// freopen("P4513_2.in","r",stdin);
// freopen("P4513.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
for(int i=1;i<=m;i++)
{
int op,x,y;
scanf("%d",&op);
if(op==2)
{
scanf("%d%d",&x,&y);
modify(1,x,y);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",query(1,min(x,y),max(x,y)).ans);
}
}
return 0;
}
by Micnation_AFO @ 2022-08-12 20:20:58
@Sktic query
是不是写错了,r <= mid
的时候说明答案都在左半边,此时返回左子树,但是您的代码是 l <= mid
的时候返回左子树,右子树的情况同理
by Sktic @ 2022-08-13 08:49:52
草,我原本是这样写的,但是这样写连样例都过不去/yun ,莫名其妙输出特大数