40pts,其他全tle

Into_the_Abyss @ 2024-08-13 08:36:25

#include<bits/stdc++.h>
#define maxn 1000100
#define ll long long

using namespace std;

ll a[maxn],n,k;

struct node{
    ll l,r,sum,b,min;
}t[maxn<<2];

void push_up(ll p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}

void build(ll l,ll r,ll p){
    t[p].l=l;t[p].r=r;
    if(l==r){t[p].sum=a[l];return;}
    ll mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    push_up(p);
}

void push_down(ll l,ll r,ll p){
    t[p<<1].b+=t[p].b;t[p<<1|1].b+=t[p].b;
    ll mid=l+r>>1;
    t[p<<1].sum+=t[p].b*(mid-l+1);
    t[p<<1|1].sum+=t[p].b*(r-mid);
    t[p].b=0;
}

void modify(ll lq,ll rq,ll l,ll r,ll x,ll p){
    if(l>=lq&&r<=rq){
        t[p].sum+=x*(r-l+1);
        t[p].b+=x;
        return ;
    }
    push_down(l,r,p);
    ll mid=l+r>>1;
    if(lq<=mid)modify(lq,rq,l,mid,x,p<<1);
    if(rq>mid)modify(lq,rq,mid+1,r,x,p<<1|1);
    push_up(p);
}

void dl(ll lq,ll rq,ll l ,ll r,ll x,ll p){
    if(l==r){
        t[p].sum=x;
        return ;
    }
    ll mid=l+r>>1;
    push_down(l,r,p);
    if(lq<=mid)dl(lq,rq,l,mid,x,p<<1);
    if(rq>mid)dl(lq,rq,mid+1,r,x,p<<1|1);
    push_up(p);
}

ll getsum(ll lq,ll rq,ll l,ll r,ll p){
    if(l>=lq&&r<=rq)return t[p].sum;
    ll mid=l+r>>1,ans=0;
    push_down(l,r,p);
    if(lq<=mid)ans+=getsum(lq,rq,l,mid,p<<1);
    if(rq>mid)ans+=getsum(lq,rq,mid+1,r,p<<1|1);
    return ans;
}

ll getmax(ll lq,ll rq,ll l,ll r,ll p){
    if(l==r)return t[p].sum;
    ll mid=l+r>>1,ans=-114514114514;
    push_down(l,r,p);
    if(lq<=mid)ans=max(getmax(lq,rq,l,mid,p<<1),ans);
    if(rq>mid)ans=max(getmax(lq,rq,mid+1,r,p<<1|1),ans);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;cin>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);

    while(k--){
        int opt,x,y,q;
        cin>>opt;
        if(opt==2){
            cin>>x>>y>>q;
            modify(x,y,1,n,q,1);
        }
        else if(opt==1){
            cin>>x>>y>>q;
            dl(x,y,1,n,q,1);
        }
            else{
            cin>>x>>y;
            cout<<getmax(x,y,1,n,1)<<"\n";
        }
    }
    return 0;
}

by Into_the_Abyss @ 2024-08-13 08:56:49

@yiming_328 em,有点晕，没太懂(哭

by yiming_328 @ 2024-08-13 08:59:08

@Into_the_Abyss 求区间最值，你的sum维护的是区间和，查询函数（getmax）相当于把树遍历了一遍

by xuduang @ 2024-08-13 09:00:51

你 getmax 递归到底了，复杂度 O(n) 的。

by Into_the_Abyss @ 2024-08-13 09:02:38

@yiming_328 奥，所以我再维护一个maxn

by Into_the_Abyss @ 2024-08-13 09:03:01

@xuduang @yiming_328 thx

by Air_Color5 @ 2024-08-13 09:05:28

@1_plus_1_equal_5 抱歉，好像是 n^2 的/wul

by Into_the_Abyss @ 2024-08-13 09:45:03

@yiming_328 现在是onlyAC on#1#3

qwq

求求dalao，刚学线段树，代码可能有点离谱qwq

#include<bits/stdc++.h>
#define maxn 1000100
#define ll long long

using namespace std;

ll a[maxn],n,k;

struct node{
    ll l,r,maxx,b,c;
}t[maxn<<2];

void push_up(ll p){
    t[p].maxx=max(t[p<<1].maxx,t[p<<1|1].maxx);
}

void build(ll l,ll r,ll p){
    t[p].l=l;t[p].r=r;
    if(l==r){t[p].maxx=a[l];return;}
    ll mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    push_up(p);
}

void push_down(ll l,ll r,ll p){
    t[p<<1].b+=t[p].b;t[p<<1|1].b+=t[p].b;
    ll mid=l+r>>1;
    t[p<<1].maxx+=t[p].b*(mid-l+1);
    t[p<<1|1].maxx+=t[p].b*(r-mid);
    t[p].b=0;
}
void push_down_2(ll p){
    t[p<<1].maxx=t[p].c;
    t[p<<1|1].maxx=t[p].c;
    t[p].c=0;
}
void modify(ll lq,ll rq,ll l,ll r,ll x,ll p){
    if(l>=lq&&r<=rq){
        t[p].maxx+=x*(r-l+1);
        t[p].b+=x;
        return ;
    }
    push_down(l,r,p);
    push_down_2(p);
    ll mid=l+r>>1;
    if(lq<=mid)modify(lq,rq,l,mid,x,p<<1);
    if(rq>mid)modify(lq,rq,mid+1,r,x,p<<1|1);
    push_up(p);
}

void dl(ll lq,ll rq,ll l ,ll r,ll x,ll p){
    if(l>=lq&&r<=rq){
        t[p].maxx=x;
        t[p].c=x;
        return ;
    }

    ll mid=l+r>>1;
    push_down(l,r,p);
    push_down_2(p);
    if(lq<=mid)dl(lq,rq,l,mid,x,p<<1);
    if(rq>mid)dl(lq,rq,mid+1,r,x,p<<1|1);
    push_up(p);
}

ll getmax(ll lq,ll rq,ll l,ll r,ll p){
    if(l>=lq&&r<=rq)return t[p].maxx;
    ll mid=l+r>>1,ans=-114514114514;
    push_down(l,r,p);
    push_down_2(p);
    if(lq<=mid)ans=max(getmax(lq,rq,l,mid,p<<1),ans);
    if(rq>mid)ans=max(getmax(lq,rq,mid+1,r,p<<1|1),ans);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;cin>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);

    while(k--){
        int opt,x,y,q;
        cin>>opt;
        if(opt==2){
            cin>>x>>y>>q;
            modify(x,y,1,n,q,1);
        }
        else if(opt==1){
            cin>>x>>y>>q;
            dl(x,y,1,n,q,1);
        }
        else{
            cin>>x>>y;
            cout<<getmax(x,y,1,n,1)<<"\n";
        }
    }
    return 0;
}

by yiming_328 @ 2024-08-13 10:58:02

@Into_the_Abyss 区间最值更新和懒标记打错了

by yiming_328 @ 2024-08-13 11:03:13

而且push_down2也打错了，如果没看错的话，c是修改的懒标记，但不用修改时，你就把maxx改成0了

by yiming_328 @ 2024-08-13 11:05:58

@Into_the_Abyss 然后两个pushdown的顺序写错了，应该先修改再加，修改可以覆盖掉前面的加法操作