笑死,一个点没过样例

P4513 小白逛公园

Anonymely @ 2022-07-03 10:59:48

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1000005;
const int inf=1e18;

namespace fastIO{
    template<typename T> void read(T &x){
        x=0;
        char ch=getchar();T fl=1;
        while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();};
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
        x=x*fl;
    }
    template<typename T> void readarray(T n,T a[]){
        for(int i=1;i<=n;i++)read(a[i]);
    }
    template<typename T> void write(T x){
        if(x<0){
            x=-x;putchar('-');
        }
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
    void readstr(string &s){
        char ch=getchar();
        while(ch!=' '||ch!='\n'){
            s+=ch;  
            ch=getchar();
        }
    }
}

using namespace fastIO;
int n,m;
int a[N];
struct tree{
    int l,r;
    int sum;
    int val,lv,rv;
    tree(){
        //sum=val=lv=rv=0;
    }
}t[N<<2];

int lson(int p){return p<<1;}
int rson(int p){return (p<<1)|1;}
int md(int l,int r){return (l+r)>>1;}
void pushup(int p){
    t[p].sum=t[lson(p)].sum+t[rson(p)].sum;
    t[p].val=max(max(t[lson(p)].val,t[rson(p)].val),t[lson(p)].rv+t[rson(p)].lv);
    t[p].lv=max(t[lson(p)].lv,t[rson(p)].lv+t[lson(p)].sum);
    t[p].rv=max(t[rson(p)].rv,t[lson(p)].rv+t[rson(p)].sum);
}

void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        t[p].val=t[p].lv=t[p].rv=a[l];
        return ;
    }
    int mid=md(l,r);
    build(lson(p),l,mid);
    build(rson(p),mid+1,r);
    pushup(p);
}

void update(int p,int x,int k){
    if(t[p].l==t[p].r){
        t[p].sum=k;
        t[p].lv=t[p].rv=t[p].val=k;
        return ;
    }
    int mid=md(t[p].l,t[p].r);
    if(x<=mid)update(lson(p),x,k);
    else update(rson(p),x,k);
    pushup(p);
}

tree query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p];
    }
    int mid=md(t[p].l,t[p].r);
    if(r<=mid)return query(lson(p),l,r);
    else if(l>mid)return query(rson(p),l,r);
    else{
        tree lop;
        tree a,b;
        a=query(lson(p),l,r),b=query(rson(p),l,r);
        //[p].sum=a.sum+b.sum;
        t[p].val=max(max(a.val,b.val),a.rv+b.lv);
        t[p].lv=max(a.lv,b.lv+a.sum);
        t[p].rv=max(b.rv,a.rv+b.sum);
        return lop;
    }
}

signed main(){
    read(n),read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r;read(op);read(l),read(r);
        if(op==1){
            if(l>r)swap(l,r);
            write(query(1,l,r).val);
            putchar('\n');
        }else{
            update(1,l,r);
            //putchar('\n');
        }
    }
    return 0;
}

呜呜呜(

样例没过,找不到锅

大佬求助


|