MSqwq @ 2021-03-08 13:59:31
QWQ
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[8000000];
ll op,x,y;
struct qwe{
ll l,r;
ll l1,r1,sum,ma;
}t[8000000];
void pu(ll p)
{
t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].l1=max(t[p*2].l1,t[p*2].sum+t[p*2+1].l1);
t[p].r1=max(t[p*2+1].r1,t[p*2+1].sum+t[p*2].r1);
t[p].ma=max(t[p*2].ma,max(t[p*2+1].ma,t[p*2].r1+t[p*2+1].l1));
}
void build(ll p,ll x,ll y)
{
t[p].l=x;
t[p].r=y;
if(x==y)
{
t[p].l1=t[p].r1=t[p].sum=t[p].ma=a[x];
return;
}
build(p*2,x,(x+y)/2);
build(p*2+1,(x+y)/2+1,y);
pu(p);
}
void insert(ll p,ll x,ll y)
{
if(t[p].l==t[p].r)
{
t[p].l1=t[p].r1=t[p].ma=t[p].sum=y;
return;
}
ll mm=(t[p].l+t[p].r)/2;
if(x<=mm)insert(p*2,x,y);
else insert(p*2+1,x,y);
pu(p);
}
qwe ask(ll p,ll x,ll y)
{
if(x<=t[p].l&&t[p].r<=y)return t[p];
ll mm=(t[p].l+t[p].r)/2;
if(y<=mm)return ask(p*2,x,y);
else
{
if(x>mm)return ask(p*2+1,x,y);
else
{
qwe xx,tmp1=ask(p*2,x,y),tmp2=ask(p*2+1,x,y);
xx.l1=max(tmp1.l1,tmp1.sum+tmp2.l1);
xx.r1=max(tmp2.r1,tmp2.sum+tmp1.r1);
xx.ma=max(tmp1.ma,max(tmp2.ma,tmp1.r1+tmp2.l1));
return xx;
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&op,&x,&y);
if(op==1)x=min(x,y),y=max(x,y),printf("%lld\n",ask(1,x,y).ma);
else insert(1,x,y);
}
}
by Macesuted @ 2021-03-08 14:57:07
x=min(x,y),y=max(x,y)
这个信息会被覆盖。
by Lucifero @ 2021-03-08 15:15:22
%%%
by Lucifero @ 2021-03-08 15:41:44
@My_sort
swap(x,y)
同 Macesuted
by zhangboju @ 2021-03-08 16:26:58
就是说
if(op==1)x=min(x,y),y=max(x,y),printf("%lld\n",ask(1,x,y).ma);
大概改成
if(op==1)
{
if(x>y) swap(x,y);
printf("%lld\n",ask(1,x,y).ma);
}
by MSqwq @ 2021-03-08 21:45:30
@Gray_White 谢谢
by MSqwq @ 2021-03-08 21:45:55
@zhangboju 谢谢qwq
by MSqwq @ 2021-03-08 21:50:45
@Macesuted 谢谢呀qwq