萌新求助，TLE on #5~#10

kbzcz @ 2022-08-18 11:21:51

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll a[N],t[N<<2],lz1[N<<2],lz2[N<<2];
void push_up(int p){ t[p]=max(t[p<<1],t[p<<1|1]); }
void push_down(int l,int r,int p) {
    int mid=(l+r)/2;
    if(lz2[p]!=-1e18) {
        t[p<<1]=lz2[p];
        lz1[p<<1]=0;
        lz2[p<<1]=lz2[p];
        t[p<<1|1]=lz2[p];
        lz1[p<<1|1]=0;
        lz2[p<<1|1]=lz2[p];
        lz2[p]=-1e18;
    }
    if(lz1[p]) {
        t[p<<1]+=lz1[p];
        t[p<<1|1]+=lz1[p];
        lz1[p<<1]+=lz1[p];
        lz1[p<<1|1]+=lz1[p];
        lz1[p]=0;
    }
}
void bt(int l,int r,int p) {
    lz2[p]=-1e18;
    if(l==r) t[p]=a[l];
    else {
        int mid=(l+r)/2;
        bt(l,mid,p<<1);
        bt(mid+1,r,p<<1|1);
        push_up(p);
    }
}
void change_add(int l,int r,int p,int x,int y,ll k) {
    if(l>=x&&r<=y) {
        t[p]+=k;
        lz1[p]+=k;
        return ;
    }
    push_down(l,r,p);
    int mid=(l+r)>>1;
    if(mid>=x) change_add(l,mid,p<<1,x,y,k);
    if(mid+1<=y) change_add(mid+1,r,p<<1|1,x,y,k);
    push_up(p);
}
void change_ti(int l,int r,int p,int x,int y,ll k) {
    if(l>=x&&r<=y) {
        t[p]=k;
        lz2[p]=k;
        return ;
    }
    push_down(l,r,p);
    int mid=(l+r)>>1;
    if(mid>=x) change_ti(l,mid,p<<1,x,y,k);
    if(mid+1<=y) change_ti(mid+1,r,p<<1|1,x,y,k);
    push_up(p);
}
ll query(int l,int r,int p,int x,int y) {
    ll mx=-1e18;
    if(l>=r&&r<=y) return t[p];
    push_down(l,r,p);
    int mid=(l+r)/2;
    if(mid>=x) mx=max(query(l,mid,p<<1,x,y),mx);
    if(mid+1<=y) mx=max(mx,query(mid+1,r,p<<1|1,x,y));
    return mx; 
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    bt(1,n,1);
    for(int i=1;i<=m;i++) {
        int f,x,y;
        ll k;
        scanf("%d%d%d",&f,&x,&y);
        if(f==1) {
            scanf("%lld",&k);
            change_ti(1,n,1,x,y,k);
        }
        else if(f==2) {
            scanf("%lld",&k);
            change_add(1,n,1,x,y,k);
        } 
        else {
            printf("%lld\n",query(1,n,1,x,y));
        }
    }
}

by _l_l_ @ 2022-08-18 11:24:47

@kbzcz query 函数中第一个 if 内错了

by kbzcz @ 2022-08-18 11:27:05

wssb

by kbzcz @ 2022-08-18 11:27:46

@_ll 改了之后TLE变WA

by kbzcz @ 2022-08-18 11:34:00

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll a[N],t[N<<2],lz1[N<<2],lz2[N<<2];
void push_up(int p){ t[p]=max(t[p<<1],t[p<<1|1]); }
void push_down(int l,int r,int p) {
    int mid=(l+r)/2;
    if(lz2[p]!=-1e18) {
        t[p<<1]=lz2[p];
        lz1[p<<1]=0;
        lz2[p<<1]=lz2[p];
        t[p<<1|1]=lz2[p];
        lz1[p<<1|1]=0;
        lz2[p<<1|1]=lz2[p];
        lz2[p]=-1e18;
    }
    if(lz1[p]) {
        t[p<<1]+=lz1[p];
        t[p<<1|1]+=lz1[p];
        lz1[p<<1]+=lz1[p];
        lz1[p<<1|1]+=lz1[p];
        lz1[p]=0;
    }
}
void bt(int l,int r,int p) {
    lz2[p]=-1e18;
    if(l==r) t[p]=a[l];
    else {
        int mid=(l+r)/2;
        bt(l,mid,p<<1);
        bt(mid+1,r,p<<1|1);
        push_up(p);
    }
}
void change_add(int l,int r,int p,int x,int y,ll k) {
    if(l>=x&&r<=y) {
        t[p]+=k;
        lz1[p]+=k;
        return ;
    }
    push_down(l,r,p);
    int mid=(l+r)>>1;
    if(mid>=x) change_add(l,mid,p<<1,x,y,k);
    if(mid+1<=y) change_add(mid+1,r,p<<1|1,x,y,k);
    push_up(p);
}
void change_ti(int l,int r,int p,int x,int y,ll k) {
    if(l>=x&&r<=y) {
        t[p]=k;
        lz2[p]=k;
        return ;
    }
    push_down(l,r,p);
    int mid=(l+r)>>1;
    if(mid>=x) change_ti(l,mid,p<<1,x,y,k);
    if(mid+1<=y) change_ti(mid+1,r,p<<1|1,x,y,k);
    push_up(p);
}
ll query(int l,int r,int p,int x,int y) {
    ll mx=-1e18;
    if(l>=x&&r<=y) return t[p];
    push_down(l,r,p);
    int mid=(l+r)/2;
    if(mid>=x) mx=max(query(l,mid,p<<1,x,y),mx);
    if(mid+1<=y) mx=max(mx,query(mid+1,r,p<<1|1,x,y));
    return mx; 
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    bt(1,n,1);
    for(int i=1;i<=m;i++) {
        int f,x,y;
        ll k;
        scanf("%d%d%d",&f,&x,&y);
        if(f==1) {
            scanf("%lld",&k);
            change_ti(1,n,1,x,y,k);
        }
        else if(f==2) {
            scanf("%lld",&k);
            change_add(1,n,1,x,y,k);
        } 
        else {
            printf("%lld\n",query(1,n,1,x,y));
        }
    }
}

by _l_l_ @ 2022-08-18 11:46:48

@kbzcz change_ti 中，第一个 if 内，需要加上一条 lz1[p]=0;

by kbzcz @ 2022-08-18 11:51:00

@_ll 谢谢大佬，wssb*2