RE求救

P4513 小白逛公园

Tobiichi_Origami @ 2022-10-13 13:26:05

#include<bits/stdc++.h>
using namespace std;
struct tree{
    int l,r;
    int max=-114514;
    int lmax=-114514;
    int rmax=-114514;
    int sum=0;
}t[4000001];
int a[1000001];
int n,m;
void pushup(int u)
{
    t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    t[u].lmax=max(t[u<<1].lmax,t[u<<1].sum+t[u<<1|1].lmax);
    t[u].rmax=max(t[u<<1|1].rmax,t[u<<1|1].sum+t[u<<1].rmax);
    t[u].max=max(max(t[u<<1].max,t[u<<1|1].max),t[u<<1].rmax+t[u<<1|1].lmax);
}
void build(int u,int l,int r)
{
    t[u].l=l;t[u].r=r;
    if(l==r)
    {
        t[u].sum=t[u].max=a[l];
        t[u].lmax=t[u].rmax=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int pos,int x)
{
    if(t[u].l==pos&&t[u].r==pos)
    {
        t[u].max=t[u].sum=x;
        t[u].lmax=t[u].rmax=x;
        return ;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(mid>=pos) modify(u<<1,pos,x);
    else modify(u<<1|1,pos,x);
    pushup(u);
}
tree query(int u,int l,int r)
{
    if(t[u].l>=l&&t[u].r<=r) return t[u];
    else
    {
        int mid=(t[u].l+t[u].r)>>1;
        if(r<=mid) return query(u<<1,l,r);
        else if(l>mid) return query(u<<1|1,l,r);
        else
        {
            tree T,L=query(u<<1,l,r),R=query(u<<1|1,l,r);
            T.lmax=max(L.lmax,L.sum+R.lmax);
            T.rmax=max(R.rmax,L.rmax+R.sum);
            T.max=max(max(L.max,R.max),L.rmax+R.lmax);
            return T;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(x>y) swap(x,y); 
        if(op==1) cout<<query(1,x,y).max<<endl;
        else modify(1,x,y);
    }
    return 0;
}

by Tobiichi_Origami @ 2022-10-13 14:09:58

不用了,已经过了,swap的地方写错了我就是歌姬


|