40分代码,T了求助

P1253 扶苏的问题

小来 @ 2022-10-01 20:33:36

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
ll  n,m,a[1000001],q;
struct ming {
    ll l,r,sum,add;
    bool lazy;
} t[4000001];
void build(ll p,ll l,ll r) {
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].sum=a[l];
        return;
    }
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) build(p<<1,l,mid);
    if(r>mid) build(p<<1|1,mid+1,r);
    t[p].sum=max(t[p<<1].sum,t[p<<1|1].sum);
    return;
}
void spread(ll p) {
    if(t[p].lazy) {
        t[p<<1].sum+=t[p].add;
        t[p<<1|1].sum+=t[p].add;
        t[p<<1].add+=t[p].add;
        t[p<<1|1].add+=t[p].add;
        t[p<<1].lazy=t[p<<1|1].lazy=1;
        t[p].lazy=0;
        t[p].add=0;
    }
}
void change1(ll p,ll l,ll r,ll v) {
    if(t[p].l>=l&&t[p].r<=r) {
        t[p].add+=v;
        t[p].sum+=v;
        t[p].lazy=1;
        return;
    }
    spread(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change1(p<<1,l,r,v);
    if(r>mid) change1(p<<1|1,l,r,v);
    t[p].sum+=v;
    return;
}
void change2(ll p,ll l,ll r,ll v) {
    if(t[p].l==t[p].r&&t[p].l>=l&&t[p].r<=r) {
        t[p].sum=v;
        return;
    }
//  spread(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change2(p<<1,l,r,v);
    if(r>mid) change2(p<<1|1,l,r,v);
    t[p].sum=v;
    return;
}
ll ask(ll p,ll l,ll r) {
    if(t[p].l>=l&&t[p].r<=r&&t[p].l==t[p].r) {
        return t[p].sum;
    }
    spread(p);
    ll mid=(t[p].l+t[p].r)>>1,ans=-1e18;
    if(l<=mid) ans=max(ans,ask(p<<1,l,r));
    if(r>mid) ans=max(ans,ask(p<<1|1,l,r));
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    for(int i=1; i<=q; i++) {
        ll op,l,r,x;
        cin>>op;
        if(op==1) {
            cin>>l>>r>>x;
            change2(1,l,r,x);
        } else if(op==2) {
            cin>>l>>r>>x;
            change1(1,l,r,x);
        } else if(op==3) {
            cin>>l>>r;
            cout<<ask(1,l,r)<<endl;
        }
    }
    return 0;
}

改了好久还超时


by register_new @ 2022-10-01 20:54:56

@小来 你可以逝逝register加快读加把for循环的i++改成++i,说不定能多几分,我没什么时间把你的代码从头开始看了


by 小来 @ 2022-10-02 07:37:53

@zhuangkaiyu 哦


|