MnZn求助,调了老半天,找不到错

P4513 小白逛公园

白依尘_轩子墨 @ 2021-07-20 10:17:40

#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define lson s,mid,ls
#define rson mid+1,t,rs
using namespace std;
const int Maxn=1e6+10;
const int mod=1e9+7;
typedef long long ll;
namespace io{
    const int _SIZE=(1<<21)+1;
    char ibuf[_SIZE],*iS,*iT,c,stk[40];int tot;
#define gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,_SIZE,stdin),(iS==iT ?EOF:*iS++)):*iS++)
    template<class I>
    inline void read(I &_x){
        I fl=1;
        for(c=gc();c<'0'||c>'9';c=gc()) if(c=='-') fl=-1;
        for(_x=0;c>='0'&&c<='9';c=gc()) _x=_x*10+(c&15);
        _x*=fl;
    }
    template<class I>
    inline void prt(I _x,char ch='\0'){
        tot=0;
        if(_x<0) putchar('-'),_x*=-1;
        do{
            stk[tot++]=_x%10|48;_x/=10;
        }while(_x);
        do{
            putchar(stk[--tot]);
        }while(tot);
        if(ch)putchar(ch);
    }
}
using io::read;
using io::prt;
inline int rd(){
    static int x;int f=1;
    static char c;
    while((c=getchar())<'0'||c>'9') if(c=='-') f=-1;
    x=(c&15);
    while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15);
    return x*f;
}
int n,m;
int a[Maxn];
struct tree{
    int l,r,maxx,sum;
}st[Maxn<<2];
tree merge(tree a,tree b){
    tree c;
    c.sum=a.sum+b.sum;
    c.l=max(a.l,a.sum+b.l);
    c.r=max(b.r,b.sum+a.r);
    c.maxx=max(max(a.maxx,b.maxx),a.r+b.l);
    return c;
}
void build(int s,int t,int p){
    if(s==t){
        st[p].sum=a[s];
        st[p].l=a[s];
        st[p].r=a[s];
        st[p].maxx=a[s];
        return;
    }
    int mid=s+t>>1;
    build(lson),build(rson);
    st[p]=merge(st[ls],st[rs]);
}
tree ask(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r) return st[p];
    int mid=s+t>>1;
    if(r<=mid) return ask(l,r,lson);
    if(mid+1<=l) return ask(l,r,rson);
    tree a,b,c;
    a=ask(l,r,lson),b=ask(l,r,rson);
    c=merge(a,b);
    return c;
}
void change(int x,int k,int s,int t,int p){
    if(s==t){
        st[p].l=k;
        st[p].sum=k;
        st[p].r=k;
        st[p].maxx=k;
        return;
    }
    int mid=s+t>>1;
    if(x<=mid) return change(x,k,lson);
    if(mid+1<=x) return change(x,k,rson);
    st[p]=merge(st[ls],st[rs]);
}
int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,n,1);
    while(m--){
        int k,x,y;
        read(k),read(x),read(y);
        if(k==2) change(x,y,1,n,1);
        else{
            if(x>y) swap(x,y);
            tree ans=ask(x,y,1,n,1);
            prt(ans.maxx,'\n');
        }
    }
    return 0;
}

rt


by 白依尘_轩子墨 @ 2021-07-20 10:18:43

只有9分


by ytoi @ 2021-07-21 17:34:34

我ak ioi


by 白依尘_轩子墨 @ 2021-07-21 17:36:24

@__snowball 好!!!


|