样例不过求助

宇默昀离 @ 2021-11-13 09:48:36

#include<bits/stdc++.h>
#define lc(p) t[p*2]
#define rc(p) t[p*2+1]
using namespace std;
typedef long long ll;
const int maxn=1000010;
int a[maxn+2];
struct node{
    int l,r;
    long long val,lazy;
    ll sum,dat,lm,rm;
}t[4*maxn+2];
void merge(int p)
{
    //t[p].val=t[p*2].val+t[p*2+1].val;
    t[p].sum=lc(p).sum+rc(p).sum;
    t[p].lm=max(lc(p).lm,lc(p).sum+rc(p).lm);
    t[p].rm=max(rc(p).rm,rc(p).sum+lc(p).rm);
    t[p].dat=max(max(lc(p).dat,rc(p).dat),lc(p).rm+rc(p).lm);
}
void bulid(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].sum=t[p].dat=t[p].lm=t[p].rm=a[l];
        return;
    }
    int mid=l+r>>1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    merge(p);
} 

void change(int p,int x,int y)
{
    if(t[p].l==t[p].r) 
    {
        t[p].val=t[p].sum=t[p].dat=t[p].lm=t[p].rm=y;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<mid) change(p*2,x,y);
    else change(p*2+1,x,y);
    merge(p);
}

node query(int p,int x,int y){
    if(x<=t[p].l && y>=t[p].r) return t[p];
    int mid=t[p].l+t[p].r>>1;
    //long long ans=0;
    //if(x<=mid) ans+=query(p*2,x,y);
    //if(y>mid) ans+=query(p*2+1,x,y);
    if(y<=mid) return query(p*2,x,y);
    if(x>mid) return query(p*2+1,x,y);
    else
    {
        node ans,lt=query(p*2,x,y),rt=query(p*2+1,x,y);
        ans.dat=ans.lm=ans.rm=-0x7fffff;
        ans.sum=0;
        ans.lm=max(lt.lm,lt.sum+rt.lm);
        ans.rm=max(rt.rm,rt.sum+lt.rm);
        ans.dat=max(max(lt.dat,rt.dat),lt.dat+rt.dat);
        return ans;
    }

}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    bulid(1,1,n);
    while(m--)
    {
        int k,a,b;
        cin>>k>>a>>b;
        if(k==1)
        {
            if(a>b) swap(a,b);
            cout<<query(1,a,b).dat<<endl;
        }
        else 
        {
            change(1,a,b);
        }
    }
    return 0;
}

by OldVagrant @ 2021-11-13 09:58:54

@宇默昀离 change函数的if语句应该是if（x<=mid）

by OldVagrant @ 2021-11-13 10:00:39

因为如果当x刚好是mid的时候，你应该去右儿子里修改，右儿子的范围是t[p].l到t[p].mid，包括两个端点

by OldVagrant @ 2021-11-13 10:03:36

还有你query函数里给ans赋值的方式应该是跟merge里的一样

by OldVagrant @ 2021-11-13 10:04:33

@宇默昀离

by OldVagrant @ 2021-11-13 10:06:05

不会就照蓝书或者我这个改

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define rint register int
#define pc(x) putchar(x)
#define gc getchar
#define INF -(1<<30)
ll a[500001],n,m,tp,x,y;
inline ll read(){
    ll x=0,y=1;
    char ch=gc();
    while(!isdigit(ch)){
        if(ch=='-') y=-1;
        ch=gc();
    }while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*y;
}
inline void write(ll x){
    if(x<0) pc('-'),x=-x;
    if(x>9) write(x/10);
    pc('0'+x%10);
}
struct SegmentTree{
    ll l,r,sum,lmax,rmax,mmax;
}st[2000001],tmp;
void push_up(ll p){
    st[p].sum=st[p<<1].sum+st[p<<1|1].sum;
    st[p].lmax=max(st[p<<1].lmax,st[p<<1].sum+st[p<<1|1].lmax);
    st[p].rmax=max(st[p<<1|1].rmax,st[p<<1].rmax+st[p<<1|1].sum);
    st[p].mmax=max(max(st[p<<1].mmax,st[p<<1|1].mmax),st[p<<1].rmax+st[p<<1|1].lmax);
}
void build(ll p,ll l,ll r){
    st[p].l=l,st[p].r=r;
    if(l==r){
        st[p].sum=st[p].rmax=st[p].lmax=st[p].mmax=a[l];
        return;
    }ll mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r),push_up(p); 
}
void change(ll p,ll l,ll r,ll d){
    if(st[p].l==st[p].r){
        st[p].sum=d,st[p].lmax=d,st[p].rmax=d,st[p].mmax=d;
        return;
    }ll mid=st[p].l+st[p].r>>1;
    (l<=mid)?change(p<<1,l,r,d):change(p<<1|1,l,r,d),push_up(p);
}
SegmentTree query(ll p,ll l,ll r){
    if(l<=st[p].l&&st[p].r<=r) return st[p];
    ll mid=st[p].l+st[p].r>>1;
    if(l<=mid&&r<=mid) return query(p<<1,l,r);
    if(mid<l&&mid<r) return query(p<<1|1,l,r);
    SegmentTree x=query(p<<1,l,r),y=query(p<<1|1,l,r);
    tmp.sum=x.sum+y.sum;
    tmp.lmax=max(x.lmax,x.sum+y.lmax);
    tmp.rmax=max(y.rmax,y.sum+x.rmax);
    tmp.mmax=max(x.mmax,max(y.mmax,x.rmax+y.lmax));
    return tmp;
}
int main(){
    n=read(),m=read();
    for(rint i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(rint i=1;i<=m;i++){
        tp=read(),x=read(),y=read();
        if(tp&1){
            if(x>y) swap(x,y);
            write(query(1,x,y).mmax),pc('\n');
        }else change(1,x,x,y);
    }return 0;
}

by 宇默昀离 @ 2021-11-13 10:12:18

@初二DB07赵泽裕 谢谢大佬qwq