虫洞吞噬者 @ 2021-10-08 16:56:48
萌新线段树只有9分(A了第一个点),看了看之前的讨论也没有发现类似的错误
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n,m,sum,cnt;
int num[100100];
struct node{
int l,r,sum,lm,rm,maxn;
}tree[4000100];
void pushup(int id)
{
if(tree[id*2].rm<0&&tree[id*2+1].lm<0)tree[id].maxn=(tree[id*2].rm,tree[id*2+1].lm);
else
{
tree[id].maxn=0;
if(tree[id*2].rm>0)tree[id].maxn+=tree[id*2].rm;
if(tree[id*2+1].lm>0)tree[id].maxn+=tree[id*2+1].lm;
}
tree[id].maxn=max(tree[id].maxn,max(tree[id*2].maxn,tree[id*2+1].maxn));
tree[id].lm=max(tree[id*2].lm,tree[id*2].sum+tree[id*2+1].lm);
tree[id].rm=max(tree[id*2+1].rm,tree[id*2].rm+tree[id*2+1].sum);
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
void build(int id,int l,int r)
{
tree[id].l=l;tree[id].r=r;tree[id].maxn=0;
if(l==r)
{
tree[id].lm=tree[id].rm=tree[id].maxn=tree[id].sum=num[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
pushup(id);
}
void add(int id,int p,int k)
{
if(tree[id].l==tree[id].r&&tree[id].l==p)
{
tree[id].lm=tree[id].rm=tree[id].maxn=tree[id].sum=k;
return;
}
int mid=(tree[id].l+tree[id].r)/2;
if(p<=mid)add(id*2,p,k);
if(p>mid)add(id*2+1,p,k);
pushup(id);
}
int find(int id,int l,int r)
{
if(l<=tree[id].l&&tree[id].r<=r)return tree[id].maxn;
int mid=(tree[id].l+tree[id].r)/2;
int ans=-0x3f3f3f3f;
if(l<=mid)ans=max(ans,find(id*2,l,r));
if(r>mid)ans=max(ans,find(id*2+1,l,r));
return ans;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&num[i]);
build(1,1,n);
for(int i=1;i<=m;++i)
{
int x,y,z;
scanf("%lld",&z);
if(z==1)
{
scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
printf("%lld\n",find(1,x,y));
}
else
{
scanf("%lld%lld",&x,&y);
add(1,x,y);
}
}
return 0;
}
by libmwlmgrimpl @ 2021-10-08 17:59:39
个人认为pushup函数写错了,那个if里面的条件好像不太对劲
你这个线段树写得好奇怪,这么长
by 虫洞吞噬者 @ 2021-10-08 18:37:52
@eddy_han 应该不会吧......能详细点一下吗QAQ
by 虫洞吞噬者 @ 2021-10-08 20:32:19
破案了,我对于本题的合并性质处理错了(find函数),和pushdown无关(实际上那个if是想要剪枝吧......)