蒟蒻0pts求助

DYhzx_QWQ @ 2023-01-13 20:48:17

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll tot,ans,t,mod,m,k,n,a,b,z;
ll x;
struct bb {
    ll l,r,mxl,mxr,mx,sum;
}tree[1000001];
void updata(ll x) {
    tree[x].sum=tree[x*2].sum+tree[x*2+1LL].sum;
    tree[x].mxl=max(tree[x*2].mxl,tree[x*2].sum+tree[x*2+1LL].mxl);
    tree[x].mxr=max(tree[x*2].mxr,tree[x*2+1LL].mxl+tree[x*2].sum);
    tree[x].mx=max(max(tree[x*2].mx,tree[x*2+1LL].mx),tree[x*2].mxr+tree[x*2+1LL].mxl);
}
void build(ll x,ll l,ll r) {
    tree[x].l=l;
    tree[x].r=r;
    if(l!=r) {
        ll mid;
        mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1LL,mid+1LL,r);
    }
    if(l==r) {
        tree[x].sum=0;
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum;
        return ;
    }
    updata(x);
}
void push(ll x,ll k,ll p) {
    if(p<tree[x].l||tree[x].r<p) return;
    if(tree[x].l==p&&tree[x].r==p) {
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum=k;
        return ; 
    }
    push(x*2,k,p);
    push(x*2+1,k,p);
    updata(x);
}
bb find(ll k,ll l,ll r)
{
    if(l<=tree[k].l&&tree[k].r<=r) return tree[k];
    ll mid=(tree[k].l+tree[k].r)/2;
    if(l<=mid) return find(k*2,l,r);
    else
    {
        if(r>mid) return find(k*2+1,l,r);
        else
        {
            bb t,a=find(k*2,l,r),b=find(k*2+1,l,r);
            t.sum=a.sum+b.sum;
            t.mxl=max(a.mxl,a.sum+b.mxl);
            t.mxr=max(a.mxr,b.mxl+a.sum);
            t.mx=max(max(a.mx,b.mx),a.mxr+b.mxl);
            return t;
        }
    }
}
int main() {
    cin>>n>>m;
    build(1LL,1LL,n);
    for(ll i=1;i<=n;i++) {
        cin>>x;
        push(1,1,x);
    }
    for(ll i=1;i<=m;i++) {
        cin>>x;
        if(x==1) {
            cin>>a>>b;
            if(a>b) swap(a,b);
            cout<<find(1LL,a,b).mx<<endl;
        }
        else {
            cin>>a>>b;
            push(1,a,b);
        }
    }
    return 0;
}

by bamboo12345 @ 2023-01-13 20:53:22

@DYhuangzixin 你那个updata的mxr肯定不对的啊

by DYhzx_QWQ @ 2023-01-13 20:56:43

by DYhzx_QWQ @ 2023-01-13 20:58:52

还是挂了

by DYhzx_QWQ @ 2023-01-13 21:00:30

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll tot,ans,t,mod,m,k,n,a,b,z;
ll x;
struct bb {
    ll l,r,mxl,mxr,mx,sum;
}tree[1000001];
void updata(ll x) {
    tree[x].sum=tree[x*2].sum+tree[x*2+1LL].sum;
    tree[x].mxl=max(tree[x*2].mxl,tree[x*2].sum+tree[x*2+1LL].mxl);
    tree[x].mxr=max(tree[x*2+1].mxr,tree[x*2].mxr+tree[x*2+1LL].sum);
    tree[x].mx=max(max(tree[x*2].mx,tree[x*2+1LL].mx),tree[x*2].mxr+tree[x*2+1LL].mxl);
}
void build(ll x,ll l,ll r) {
    tree[x].l=l;
    tree[x].r=r;
    if(l!=r) {
        ll mid;
        mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1LL,mid+1LL,r);
    }
    if(l==r) {
        tree[x].sum=0;
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum;
        return ;
    }
    updata(x);
}
void push(ll x,ll k,ll p) {
    if(p<tree[x].l||tree[x].r<p) return;
    if(tree[x].l==p&&tree[x].r==p) {
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum=k;
        return ; 
    }
    push(x*2,k,p);
    push(x*2+1,k,p);
    updata(x);
}
bb find(ll k,ll l,ll r)
{
    if(l<=tree[k].l&&tree[k].r<=r) return tree[k];
    ll mid=(tree[k].l+tree[k].r)/2;
    if(l<=mid) return find(k*2,l,r);
    else
    {
        if(r>mid) return find(k*2+1,l,r);
        else
        {
            bb t,a=find(k*2,l,r),b=find(k*2+1,l,r);
            t.sum=a.sum+b.sum;
            t.mxl=max(a.mxl,a.sum+b.mxl);
            t.mxr=max(b.mxr,a.mxr+b.sum);
            t.mx=max(max(a.mx,b.mx),a.mxr+b.mxl);
            return t;
        }
    }
}
int main() {
    cin>>n>>m;
    build(1LL,1LL,n);
    for(ll i=1;i<=n;i++) {
        cin>>x;
        push(1,1,x);
    }
    for(ll i=1;i<=m;i++) {
        cin>>x;
        if(x==1) {
            cin>>a>>b;
            if(a>b) swap(a,b);
            cout<<find(1LL,a,b).mx<<endl;
        }
        else {
            cin>>a>>b;
            push(1,a,b);
        }
    }
    return 0;
}

by bamboo12345 @ 2023-01-13 21:04:59

@DYhuangzixin find的一堆if条件写错了，自己理理，还有数组开到要求的4倍最好

by DYhzx_QWQ @ 2023-01-13 21:07:05

ok

by DYhzx_QWQ @ 2023-01-13 21:26:48

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll tot,ans,t,mod,m,k,n,a,b,z;
ll x;
struct bb {
    ll l,r,mxl,mxr,mx,sum;
}tree[2000001];
void updata(ll x) {
    tree[x].sum=tree[x*2].sum+tree[x*2+1LL].sum;
    tree[x].mxl=max(tree[x*2].mxl,tree[x*2].sum+tree[x*2+1LL].mxl);
    tree[x].mxr=max(tree[x*2+1].mxr,tree[x*2].mxr+tree[x*2+1LL].sum);
    tree[x].mx=max(max(tree[x*2].mx,tree[x*2+1LL].mx),tree[x*2].mxr+tree[x*2+1LL].mxl);
}
void build(ll x,ll l,ll r) {
    tree[x].l=l;
    tree[x].r=r;
    if(l!=r) {
        ll mid;
        mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1LL,mid+1LL,r);
    }
    if(l==r) {
        tree[x].sum=0;
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum;
        return ;
    }
    updata(x);
}
void push(ll x,ll k,ll p) {
    if(p<tree[x].l||tree[x].r<p) return;
    if(tree[x].l==p&&tree[x].r==p) {
        tree[x].mxl=tree[x].mxr=tree[x].mx=tree[x].sum=k;
        return ; 
    }
    push(x*2,k,p);
    push(x*2+1,k,p);
    updata(x);
}
bb find(ll k,ll l,ll r)
{
    if(l<=tree[k].l&&tree[k].r<=r) return tree[k];
    ll mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return find(k*2,l,r);
    else
    {
        if(l>mid) return find(k*2+1,l,r);
        else
        {
            bb t,a=find(k*2,l,r),b=find(k*2+1,l,r);
            t.sum=a.sum+b.sum;
            t.mxl=max(a.mxl,a.sum+b.mxl);
            t.mxr=max(b.mxr,a.mxr+b.sum);
            t.mx=max(max(a.mx,b.mx),a.mxr+b.mxl);
            return t;
        }
    }
}
int main() {
    cin>>n>>m;
    build(1LL,1LL,n);
    for(ll i=1;i<=n;i++) {
        cin>>x;
        push(1,1,x);
    }
    for(ll i=1;i<=m;i++) {
        cin>>x;
        if(x==1) {
            cin>>a>>b;
            if(a>b) swap(a,b);
            cout<<find(1LL,a,b).mx<<endl;
        }
        else {
            cin>>a>>b;
            push(1,a,b);
        }
    }
    return 0;
}