求助线段树水题

P4513 小白逛公园

Green_Bird @ 2020-08-31 11:40:30

只对了一个点,自己感觉没错
请求各位大佬帮忙看一下代码
或是提供一组数据(可以调的那种)
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int c[N];
struct tree{
    int l,r,sum,lm,rm,m;
}a[N*4];
int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}

void Add(int k)
{
    a[k].sum=a[ls(k)].sum+a[rs(k)].sum;
    a[k].lm=max(a[ls(k)].lm,a[ls(k)].sum+a[rs(k)].lm);
    a[k].rm=max(a[rs(k)].rm,a[rs(k)].sum+a[ls(k)].rm);
    a[k].m=max(max(a[ls(k)].lm,a[rs(k)].rm),a[ls(k)].rm+a[rs(k)].lm);
}
void build(int k,int l,int r)
{
    a[k].l=l;a[k].r=r;
    if(l==r)
    {
        a[k].lm=a[k].rm=a[k].m=a[k].sum=c[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    Add(k);
}
void change(int k,int x,int c)
{
    int l=a[k].l,r=a[k].r;
    if(l==r)
    {
        a[k].sum=a[k].lm=a[k].rm=a[k].m=c;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(ls(k),x,c);
    else change(rs(k),x,c);
    Add(k);
}
tree Ask(int k,int x,int y)
{
    int l=a[k].l,r=a[k].r;
    if(x<=l&&y>=r) return a[k];
    int mid=(l+r)>>1;
    int res=-99999999;
    if(y<=mid) return Ask(ls(k),x,y);
    else if(mid+1<=x) return Ask(rs(k),x,y);
         else
         {
             tree a,b,c;
             a=Ask(ls(k),x,y);b=Ask(rs(k),x,y);
             c.sum=a.sum+b.sum;
             c.lm=max(a.lm,a.sum+b.lm);
             c.rm=max(b.rm,b.sum+a.rm);
             c.m=max(max(a.lm,b.rm),a.rm+b.lm);
             return c;
         }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    c[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int k,x,y;
        k=read();x=read();y=read();
        if(k==1)
        {
            if(x>y) swap(x,y);
            tree a=Ask(1,x,y);
            cout<<a.m<<endl;
        }
        else change(1,x,y);
    }
    return 0;
}

by vijone @ 2020-08-31 11:58:06

c.m=max(max(a.lm,b.rm),a.rm+b.lm);

可能是这一句出问题了吧。

max(a.lm,b.rm)改成max(a.m,b.m)试试

by vijone @ 2020-08-31 11:59:53

@Green_Bird


by vijone @ 2020-08-31 12:05:04

另外 add 函数也要改


void Add(int k)
{
    a[k].sum=a[ls(k)].sum+a[rs(k)].sum;
    a[k].lm=max(a[ls(k)].lm,a[ls(k)].sum+a[rs(k)].lm);
    a[k].rm=max(a[rs(k)].rm,a[rs(k)].sum+a[ls(k)].rm);
    a[k].m=max(max(a[ls(k)].lm,a[rs(k)].rm),a[ls(k)].rm+a[rs(k)].lm);
    a[k].m=max(a[k].m,max(a[ls(k)].m,a[rs(k)].m)) ;加上这一句
}

by Green_Bird @ 2020-08-31 12:07:11

@vijone 感谢大佬,调了好久,终于对了


by Green_Bird @ 2020-08-31 12:11:58

@vijone

void Add(int k)
{
    a[k].sum=a[ls(k)].sum+a[rs(k)].sum;
    a[k].lm=max(a[ls(k)].lm,a[ls(k)].sum+a[rs(k)].lm);
    a[k].rm=max(a[rs(k)].rm,a[rs(k)].sum+a[ls(k)].rm);
    a[k].m=max(max(a[ls(k)].lm,a[rs(k)].rm),a[ls(k)].rm+a[rs(k)].lm);才发现这句是错的
}

当前节点的最大子段和应该是:

a[k].m=max(max(a[ls(k)].m,a[rs(k)].m),a[ls(k)].rm+a[rs(k)].lm);

|