SigmaXTH @ 2018-10-19 08:08:06
#include <bits/stdc++.h>
using namespace std;
#define ll(x) x*2
#define rr(x) x*2+1
#define lt long long
lt n,m,sen[500005],sgm[2005005],L[2005005],R[2005005],Max[2005005],flag,lx,rx,ans,lans,rans;
inline lt read()
{
char ch=getchar();lt f=1,w=0;
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-48;ch=getchar();}
return f*w;
}
inline void hb(lt node){
Max[node]=max(max(Max[ll(node)],Max[rr(node)]),R[ll(node)]+L[rr(node)]);
L[node]=max(L[ll(node)],sgm[ll(node)]+L[rr(node)]);
R[node]=max(R[rr(node)],sgm[rr(node)]+R[ll(node)]);
sgm[node]=sgm[ll(node)]+sgm[rr(node)];
return;
}
inline void build(lt node,lt left,lt right){
if(left>right) return;
if(left==right)
{
Max[node]=sgm[node]=L[node]=R[node]=sen[left];return;
}
lt dist=(left+right)>>1;
build(ll(node),left,dist);
build(rr(node),dist+1,right);
hb(node);
return;
}
inline void insert(lt node,lt left,lt right,lt l,lt r,lt v){
if(left==right)
{
Max[node]=sgm[node]=L[node]=R[node]=v;return;
}
lt dist=(left+right)>>1;
if(r<=dist) insert(ll(node),left,dist,l,r,v);
else insert(rr(node),dist+1,right,l,r,v);
hb(node);
return;
}
inline void check(lt node,lt left,lt right,lt l,lt r,lt &ans,lt &lans,lt &rans)
{
if(left>r||right<l) return;
if(left>=l&&right<=r){
ans=Max[node];lans=L[node];rans=R[node];return;
}
lt dist=(left+right)>>1;
if(r<=dist) check(ll(node),left,dist,l,r,ans,lans,rans);
else if(l>dist) check(rr(node),dist+1,right,l,r,ans,lans,rans);
else
{
lt Lans,Llans,Lrans,Rans,Rlans,Rrans;
Lans=Llans=Lrans=Rans=Rlans=Rrans=0;
check(ll(node),left,dist,l,r,Lans,Llans,Lrans);
check(rr(node),dist+1,right,l,r,Rans,Rlans,Rrans);
ans=max(max(Lans,Rans),Lrans+Rlans);
lans=max(lans,sgm[ll(node)]+Rlans);
rans=max(rans,sgm[rr(node)]+Lrans);
}
}
int main()
{
ios::sync_with_stdio(false);
n=read();m=read();
for(lt i=1;i<=n;++i){sen[i]=read();}
build(1,1,n);
for(lt i=1;i<=m;++i){
flag=read();lx=read();rx=read();
if(flag==1)
{
if(lx>rx) swap(lx,rx);
ans=lans=rans=0;
check(1,1,n,lx,rx,ans,lans,rans);
cout<<ans<<endl;
}
else
{
insert(1,1,n,lx,lx,rx);
}
}
return 0;
}
有哪位巨佬能帮蒟蒻看一看是哪里出了问题吗?? 已经调了N遍9分了qwq....