样例一过不去,已调吐,玄关

P1253 扶苏的问题

Saint_yu @ 2023-12-21 14:08:06

#include <bits/stdc++.h>
#define MAXN 1000005
#define INF 1000000000005
typedef long long lol;
using namespace std;
int n,q,l,r,op;
lol a[MAXN],delta;
struct node{
    int l,r;
    lol lazy1=INF,lazy2=0,val; //lazy1是修改,lazy2是加 
}tree[MAXN];
lol max(lol x,lol y){return x>y?x:y;}
void make_tree(int now,int ll,int rr){
    tree[now].l=ll,tree[now].r=rr;
    if(tree[now].l==tree[now].r){
        tree[now].val=a[now];
        return ;
    }
    int mid=(ll+rr)>>1;
    make_tree(now<<1,ll,mid);
    make_tree(now<<1|1,mid+1,rr);
    tree[now].val=max(tree[now<<1].val,tree[now<<1|1].val);
}
void down_tag(int x){
    if(tree[x].lazy1!=INF){
        tree[x<<1].lazy2=0;
        tree[x<<1].lazy1=tree[x].lazy1;
        tree[x<<1].val=tree[x].lazy1;
        tree[x<<1|1].lazy2=0;
        tree[x<<1|1].lazy1=tree[x].lazy1;
        tree[x<<1|1].val=tree[x].lazy1;
        tree[x].lazy1=INF;
    }
    if(tree[x].lazy2){
        tree[x<<1].lazy2+=tree[x].lazy2;
        tree[x<<1].val+=tree[x].lazy2;
        tree[x<<1|1].lazy2+=tree[x].lazy2;
        tree[x<<1|1].val+=tree[x].lazy2;
        tree[x].lazy2=0;
    }
}
lol query_interval(int now,int ll,int rr){
    if(tree[now].l>=ll&&tree[now].r<=rr)return tree[now].val;
    down_tag(now);
    int mid=(tree[now].l+tree[now].r)>>1;lol w=-INF;
    if(ll<=mid)w=max(w,query_interval(now<<1,ll,rr));
    if(r>mid)w=max(w,query_interval(now<<1|1,ll,rr));
    return w;
}
void change_interval(int now,int ll,int rr,int d){
    if(tree[now].l>=ll&&tree[now].r<=rr){
        tree[now].lazy2=0;
        tree[now].lazy1=d;
        tree[now].val=d; 
        return ;
    }
    down_tag(now);
    int mid=(tree[now].l+tree[now].r)>>1;
    if(ll<=mid)change_interval(now<<1,ll,rr,d);
    if(rr>mid)change_interval(now<<1|1,ll,rr,d);
    tree[now].val=max(tree[now<<1].val,tree[now<<1|1].val);
}
void add_interval(int now,int ll,int rr,int d){
    if(tree[now].l>=ll&&tree[now].r<=rr){
        tree[now].lazy2+=d;
        tree[now].val+=d; 
        return ;
    }
    down_tag(now);
    int mid=(tree[now].l+tree[now].r)>>1;
    if(ll<=mid)change_interval(now<<1,ll,rr,d);
    if(rr>mid)change_interval(now<<1|1,ll,rr,d);
    tree[now].val=max(tree[now<<1].val,tree[now<<1|1].val);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    make_tree(1,1,n);
    while(q--){
        scanf("%d%d%d",&op,&l,&r);
        if(op!=3)scanf("%lld",&delta);
        if(op==1)
            change_interval(1,l,r,delta);
        else if(op==2)
            add_interval(1,l,r,delta);
        else
            cout<<query_interval(1,l,r)<<endl;
    }
    return 0;
}

by waauto @ 2023-12-21 14:41:17

change函数里面调用的是add。


by waauto @ 2023-12-21 14:41:31

另外你可能inf设小了


by waauto @ 2023-12-21 14:42:05

口误,add函数里面调用的是change。


by waauto @ 2023-12-21 14:46:54

建树还写错了。应该是tree[now].val=a[ll]


by waauto @ 2023-12-21 14:48:03

然后你线段树没开4倍,然后就调完了。


by Saint_yu @ 2023-12-21 21:32:11

@waauto OK,已关


|