大佬求调!!悬关!!深进上的思路

P1253 扶苏的问题

Nazale_ @ 2023-10-05 20:03:47

#include <bits/stdc++.h>
#define int long long
#define mod 911451407
#define lowbit(x) x&-x
#define tk 0.99789
#define INF 1e18
typedef long long ll;
using namespace std;
const int maxn=1e6+5;
int n,q;
int op,l,r,x;
int t[maxn];
inline int read(){
    char c=getchar();
    int n=0,s=1;
    while(c<'0'||c>'9'){
        if(c=='-'){
            s=-1;
        }
        c=getchar();
    }
    while(c>='0' && c<='9'){
        n=n*10+c-'0';
        c=getchar();
    }
    return n*s;
}
struct tree{
    int l,r;
    int w;
    //加法标记,赋值标记 
    int t1,t2=INF;
}a[maxn<<2];
void pushup(int u){
    a[u].w=max(a[u*2].w,a[u*2+1].w);
}
void build(int u,int l,int r){
    a[u].l=l,a[u].r=r;
    if(l==r){
        a[u].w==t[l];
        return;
    }
    int mid=l+r>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
bool Inrange(int L,int R,int l,int r){
    return (L>=l) && (R<=r);
}
bool Outrange(int L,int R,int l,int r){
    return (L>r)||(R<l);
}
void maketag(int u,int x,int type){
    if(type==1){
        a[u].t1=0;
        a[u].t2=x;
        a[u].w=x;   
    }
    else{
        if(a[u].t2==INF){
            a[u].t1+=x;
        }
        else a[u].t2+=x;
        a[u].w+=x;
    }
}
void pushdown(int u){
    if(a[u].t2==INF){
        maketag(u*2,a[u].t1,2);
        maketag(u*2+1,a[u].t1,2);
        a[u].t1=0;
    }
    else{
        maketag(u*2,a[u].t2,1);
        maketag(u*2+1,a[u].t2,1);
        a[u].t2=INF;
    }
}
void update(int u,int l,int r,int x,int type){
    if(Inrange(a[u].l,a[u].r,l,r)){
        maketag(u,x,type);
        return;
    }
    else if(!Outrange(a[u].l,a[u].r,l,r)){
        int mid=a[u].l+a[u].r>>1;
        pushdown(u);
        update(u*2,l,r,x,type);
        update(u*2+1,l,r,x,type);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(Inrange(a[u].l,a[u].r,l,r)){
        return a[u].w;
    }
    else if(!Outrange(a[u].l,a[u].r,l,r)){
        pushdown(u);
        return max(query(u*2,l,r),query(u*2+1,l,r));
    }
    else return -INF;
}
signed main(){
    n=read();q=read();
    for (int i=1;i<=n;i++){
        t[i]=read();
    }
    build(1,1,n);
    while(q--){
        op=read();
        if(op==1){
            l=read();r=read();x=read();
            update(1,l,r,x,1);
        }
        else if(op==2){
            l=read();r=read();x=read();
            update(1,l,r,x,2);
        }
        else{
            l=read();r=read();
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by Nazale_ @ 2023-10-05 20:04:35

个人总感觉是小问题,但死活调不出来(逃)


by August_Light @ 2023-10-05 20:21:24

@Cxs_Lg builda[u].w==t[l];


by Nazale_ @ 2023-10-05 20:50:47

@August_Light woc 感谢大佬,我真的调了好久,蕾姆了


by Nazale_ @ 2023-10-05 20:51:34

@August_Light 已关注 %%%细心的大佬


by Nazale_ @ 2023-10-05 20:52:04

此帖结!!!


|