线段树40pts求调

P1253 扶苏的问题

witness_cy @ 2022-11-15 21:04:49

%%%求助大佬,区间赋值后玄学输出一个极大值,还不是我赋值的最大值

#include<cstdio>
#include<iostream> 
using namespace std;

#define int long long
#define inf 1e18
#define N 1000005

struct node{
    int l,r;
    long long val,tag1,tag2;
}seg[4*N];

int n,q,op,x,y,t,ans,a[N];

bool in(int L,int R,int nl,int nr){
    return L>=nl&&R<=nr;
}

bool out(int L,int R,int nl,int nr){
    return L>nr||R<nl;
}

void mtag2(int u,int nl,int nr,int k){
    seg[u].val+=k;
    if(seg[u].tag1!=inf) seg[u].tag1+=k;
    else seg[u].tag2+=k;
}

void mtag1(int u,int nl,int nr,int k){
    seg[u].val=seg[u].tag1=k;seg[u].tag2=0;
}

void pushup(int u){
    seg[u].val=max(seg[u*2].val,seg[u*2+1].val);
}

void pushdown(int u,int nl,int nr){
    int mid=(nl+nr)/2;
    if(seg[u].tag1!=inf){
        mtag1(u*2,nl,mid,seg[u].tag1);
        mtag1(u*2+1,mid+1,nr,seg[u].tag1),seg[u].tag1=inf;
    }
    else{
        mtag2(u*2,nl,mid,seg[u].tag2);
        mtag2(u*2+1,mid+1,nr,seg[u].tag2),seg[u].tag2=0;
    }
}

void update(int typ,int u,int nl,int nr,int L,int R,int k){

    if(in(nl,nr,L,R)){
        if(typ==1) mtag1(u,nl,nr,k);
        else mtag2(u,nl,nr,k);
    }
    else if(!out(nl,nr,L,R)){
        pushdown(u,nl,nr);
        int mid=(nl+nr)/2;
        update(typ,u*2,nl,mid,L,R,k),update(typ,u*2+1,mid+1,nr,L,R,k);
        pushup(u);
    }
} 

int query(int u,int nl,int nr,int L,int R){

    if(in(nl,nr,L,R)) return seg[u].val;

    else if(!out(nl,nr,L,R)){
        pushdown(u,nl,nr);
        int mid=(nl+nr)/2;
        return max(query(u*2,nl,mid,L,R),query(u*2+1,mid+1,nr,L,R));
    }
    else return -0x7fffffffff;
}

void build(int u,int nl,int nr){
    seg[u].l=nl,seg[u].r=nr,seg[u].tag1=inf,seg[u].tag2=0;

    if(nl==nr){seg[u].val=a[nl];return;}

    int mid=(nl+nr)/2;
    build(u*2,nl,mid),build(u*2+1,mid+1,nr); 
    pushup(u);
}

signed main(){

    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);

    while(q--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1) scanf("%d",&t),update(1,1,1,n,x,y,t);
        else if(op==2) scanf("%d",&t),update(2,1,1,n,x,y,t);
        else printf("%lld\n",query(1,1,n,x,y));
    }
    return 0;
}

by witness_cy @ 2022-12-07 07:37:10

我是sb,最大值给自己开炸了,此贴完结


|