MnZn求助线段树qwq

二叉苹果树 @ 2022-08-05 22:56:46

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;

long long read()
{
    long long w=1,q=0;
    char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))
        ch=getchar();
    if(ch=='-')
        w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
        q=(q<<1)+(q<<3)+ch-'0',ch=getchar();
    return w*q;
}

int n,m,k;
struct Node
{
    int MAX,maxl,maxr,sum;
}T[maxn<<2];

long long a[maxn],mul[maxn<<2],laz[maxn<<2];

void up(int i)
{
    int ls=i<<1,rs=((i<<1)|1);
    if(T[ls].maxl<0&&T[rs].maxr<0)
        T[i].MAX=max(T[ls].maxr,T[rs].maxl);
    else
    {
        T[i].MAX=0;
        if(T[ls].maxr>0)
            T[i].MAX+=T[ls].maxr;
        if(T[rs].maxr>0)
            T[i].MAX+=T[rs].maxl;
    }
    T[i].MAX=max(T[i].MAX,T[ls].MAX);
    T[i].MAX=max(T[i].MAX,T[rs].MAX);
    T[i].maxl=max(T[ls].maxl,T[ls].sum+T[rs].maxl);
    T[i].maxr=max(T[rs].maxr,T[rs].sum+T[ls].maxr);
    T[i].sum=(T[ls].sum+T[rs].sum);
}

void change(int i,int s,int t,int p,int v)
{
    if(s==t)
    {
        T[i].MAX=T[i].maxl=T[i].maxr=T[i].sum;
        return ;
    }
    int mid=s+((t-s)>>1);
    if(p<=mid)
        change(i<<1,s,mid,p,v);
    else
        change(i<<1|1,mid+1,t,p,v);
    up(i);
}

void build(int s,int t,int i)
{
    if(s==t)
    {
        T[i].sum=T[i].maxl=T[i].maxr=T[i].MAX=a[s];
        return ;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,i<<1);
    build(mid+1,t,i<<1|1);
    up(i);
}

Node query(int l,int r,int i,int s,int t)
{
    if(l<=s&&t<=r)
        return T[i];
    int mid=s+((t-s)>>1);
    Node res,A,B;
    if(mid>=r)
        return query(l,r,i<<1,s,mid);
    if(mid<l)
        return query(l,r,(i<<1)|1,mid+1,s);
    A=query(l,r,i<<1,s,mid);
    B=query(l,r,(i<<1)|1,mid+1,s);
    res.maxl=max(A.maxl,A.sum+B.maxl);
    res.maxr=max(B.maxr,B.sum+A.maxr);
    res.MAX=max(max(A.MAX,B.MAX),A.maxr+B.maxl);
    res.sum=A.sum+B.sum;
    return res;

}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        k=read();
        if(k==1)
        {
            int a,b;
            a=read(),b=read();
            if(a>b)
                swap(a,b);
            printf("%d\n",query(1,n,1,a,b).MAX);
        }
        else
        {
            int p,s;
            p=read(),s=read();
            change(1,1,n,p,s);
        }
    }
    return 0;
}

by 二叉苹果树 @ 2022-08-05 23:05:57

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;

long long read()
{
    long long w=1,q=0;
    char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))
        ch=getchar();
    if(ch=='-')
        w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
        q=(q<<1)+(q<<3)+ch-'0',ch=getchar();
    return w*q;
}

int n,m,k;
struct Node
{
    int MAX,maxl,maxr,sum;
}T[maxn<<2];

long long a[maxn],mul[maxn<<2],laz[maxn<<2];

void up(int i)
{
    int ls=i<<1,rs=((i<<1)|1);
    T[i].MAX=max(T[i].MAX,T[ls].MAX);
    T[i].MAX=max(T[i].MAX,T[rs].MAX);
    T[i].maxl=max(T[ls].maxl,T[ls].sum+T[rs].maxl);
    T[i].maxr=max(T[rs].maxr,T[rs].sum+T[ls].maxr);
    T[i].sum=(T[ls].sum+T[rs].sum);
}

void change(int i,int s,int t,int p,int v)
{
    if(s==t)
    {
        T[i].MAX=T[i].maxl=T[i].maxr=T[i].sum=v;
        return ;
    }
    int mid=s+((t-s)>>1);
    if(p<=mid)
        change(i<<1,s,mid,p,v);
    else
        change(i<<1|1,mid+1,t,p,v);
    up(i);
}

void build(int s,int t,int i)
{
    if(s==t)
    {
        T[i].sum=T[i].maxl=T[i].maxr=T[i].MAX=a[s];
        return ;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,i<<1);
    build(mid+1,t,i<<1|1);
    up(i);
}

Node query(int l,int r,int i,int s,int t)
{
    if(l<=s&&t<=r)
        return T[i];
    int mid=s+((t-s)>>1);
    Node res,A,B;
    if(mid>=r)
        return query(l,r,i<<1,s,mid);
    if(mid<l)
        return query(l,r,(i<<1)|1,mid+1,s);
    A=query(l,r,i<<1,s,mid);
    B=query(l,r,(i<<1)|1,mid+1,s);
    res.sum=A.sum+B.sum;
    res.maxl=max(A.maxl,A.sum+B.maxl);
    res.maxr=max(B.maxr,B.sum+A.maxr);
    res.MAX=max(max(A.MAX,B.MAX),A.maxr+B.maxl);
    return res;

}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        k=read();
        if(k==1)
        {
            int a,b;
            a=read(),b=read();
            if(a>b)
                swap(a,b);
            printf("%d\n",query(1,n,1,a,b).MAX);
        }
        else
        {
            int p,s;
            p=read(),s=read();
            change(1,1,n,p,s);
        }
    }
    return 0;
}

修改了一下，仍错误

by 二叉苹果树 @ 2022-08-05 23:18:09

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;

long long read()
{
    long long w=1,q=0;
    char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))
        ch=getchar();
    if(ch=='-')
        w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
        q=(q<<1)+(q<<3)+ch-'0',ch=getchar();
    return w*q;
}

int n,m,k;
struct Node
{
    int MAX,maxl,maxr,sum;
}T[maxn<<2];

long long a[maxn],mul[maxn<<2],laz[maxn<<2];

void up(int i)
{
    int ls=i<<1,rs=((i<<1)|1);
    T[i].sum=(T[ls].sum+T[rs].sum);
    T[i].maxl=max(T[ls].sum+T[rs].maxl,T[ls].maxl);
    T[i].maxr=max(T[rs].sum+T[ls].maxr,T[rs].maxr);
    T[i].MAX=max(max(T[ls].MAX,T[rs].MAX),T[ls].maxr+T[rs].maxl);
}

void change(int i,int s,int t,int p,int v)
{
    if(s==t)
    {
        T[i].MAX=T[i].maxl=T[i].maxr=T[i].sum=v;
        return ;
    }
    int mid=s+((t-s)>>1);
    if(p<=mid)
        change(i<<1,s,mid,p,v);
    else
        change(i<<1|1,mid+1,t,p,v);
    up(i);
}

void build(int s,int t,int i)
{
    if(s==t)
    {
        T[i].sum=T[i].maxl=T[i].maxr=T[i].MAX=a[s];
        return ;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,i<<1);
    build(mid+1,t,i<<1|1);
    up(i);
}

Node query(int l,int r,int i,int s,int t)
{
    if(l<=s&&t<=r)
        return T[i];
    int mid=s+((t-s)>>1);
    Node res,A,B;
    if(mid>=r)
        return query(l,r,i<<1,s,mid);
    if(mid<l)
        return query(l,r,(i<<1)|1,mid+1,s);
    A=query(l,r,i<<1,s,mid);
    B=query(l,r,(i<<1)|1,mid+1,s);
    res.sum=A.sum+B.sum;
    res.maxl=max(A.maxl,A.sum+B.maxl);
    res.maxr=max(B.maxr,B.sum+A.maxr);
    res.MAX=max(max(A.MAX,B.MAX),A.maxr+B.maxl);
    return res;

}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        k=read();
        if(k==1)
        {
            int a,b;
            a=read(),b=read();
            if(a>b)
                swap(a,b);
            printf("%d\n",query(1,n,1,a,b).MAX);
        }
        else
        {
            int p,s;
            p=read(),s=read();
            change(1,1,n,p,s);
        }
    }
    return 0;
}

再次更新，仍然错误

by cancan123456 @ 2022-08-05 23:22:36

Line72, return query(l,r,(i<<1)|1,mid+1,s);

？？？

by cancan123456 @ 2022-08-05 23:24:09

Line 74 同理

by cancan123456 @ 2022-08-05 23:27:45

Line 97, printf("ans %d\n",query(1,n,1,a,b).MAX);

？？？

by cancan123456 @ 2022-08-05 23:27:48

@Étoiles_Brillantes

by cancan123456 @ 2022-08-05 23:28:25

然后就过了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;

long long read()
{
    long long w=1,q=0;
    char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))
        ch=getchar();
    if(ch=='-')
        w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
        q=(q<<1)+(q<<3)+ch-'0',ch=getchar();
    return w*q;
}

int n,m,k;
struct Node
{
    int MAX,maxl,maxr,sum;
}T[maxn<<2];

long long a[maxn],mul[maxn<<2],laz[maxn<<2];

void up(int i)
{
    int ls=i<<1,rs=((i<<1)|1);
    T[i].sum=(T[ls].sum+T[rs].sum);
    T[i].maxl=max(T[ls].sum+T[rs].maxl,T[ls].maxl);
    T[i].maxr=max(T[rs].sum+T[ls].maxr,T[rs].maxr);
    T[i].MAX=max(max(T[ls].MAX,T[rs].MAX),T[ls].maxr+T[rs].maxl);
}

void change(int i,int s,int t,int p,int v)
{
    if(s==t)
    {
        T[i].MAX=T[i].maxl=T[i].maxr=T[i].sum=v;
        return ;
    }
    int mid=s+((t-s)>>1);
    if(p<=mid)
        change(i<<1,s,mid,p,v);
    else
        change(i<<1|1,mid+1,t,p,v);
    up(i);
}

void build(int s,int t,int i)
{
    if(s==t)
    {
        T[i].sum=T[i].maxl=T[i].maxr=T[i].MAX=a[s];
        return ;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,i<<1);
    build(mid+1,t,i<<1|1);
    up(i);
}

Node query(int l,int r,int i,int s,int t)
{
    if(l<=s&&t<=r)
        return T[i];
    int mid=s+((t-s)>>1);
    Node res,A,B;
    if(mid>=r)
        return query(l,r,i<<1,s,mid);
    if(mid<l)
        return query(l,r,(i<<1)|1,mid+1,t);
    A=query(l,r,i<<1,s,mid);
    B=query(l,r,(i<<1)|1,mid+1,t);
    res.sum=A.sum+B.sum;
    res.maxl=max(A.maxl,A.sum+B.maxl);
    res.maxr=max(B.maxr,B.sum+A.maxr);
    res.MAX=max(max(A.MAX,B.MAX),A.maxr+B.maxl);
    return res;

}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        k=read();
        if(k==1)
        {
            int a,b;
            a=read(),b=read();
            if(a>b)
                swap(a,b);
            printf("%d\n",query(a,b,1,1,n).MAX);
        }
        else
        {
            int p,s;
            p=read(),s=read();
            change(1,1,n,p,s);
        }
    }
    return 0;
}

by 二叉苹果树 @ 2022-08-05 23:35:36

@cancan123456 感谢！

by y_kx_b @ 2023-02-01 18:57:04

烤谷 qwq