90pts求助 WAon#6

P1253 扶苏的问题

LYY_yyyy @ 2022-11-11 15:14:24

RT

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int n,m,op;
int l,r,x;
typedef long long ll;
struct node{
    int l,r;
    ll w,add,ch;
}tr[4*N];
int a[N];
inline int read()
{
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(ll x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void pushup(int u)
{
    tr[u].w=max(tr[u<<1].w,tr[u<<1|1].w);
}
void pushdown_c(int u)
{
    if(tr[u].ch!=-2e10)
    {
        tr[u<<1].add=0;
        tr[u<<1|1].add=0;
        tr[u<<1].w=tr[u<<1|1].w=tr[u].ch;
        tr[u<<1|1].ch=tr[u<<1].ch=tr[u].ch;
        tr[u].ch=-2e10;
    }   
}
void pushdown_j(int u)
{
    if(tr[u].add)
    {
        tr[u<<1].add+=tr[u].add;
        tr[u<<1].w+=tr[u].add;
        tr[u<<1|1].add+=tr[u].add;
        tr[u<<1|1].w+=tr[u].add;
        tr[u].add=0;
    }
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].ch=-2e10;
    if(l==r)
    {
        tr[u].w=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void change(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&r>=tr[u].r)
    {
        tr[u].add=0;
        tr[u].w=x;
        tr[u].ch=x;
        return;
    }
    pushdown_c(u);
    pushdown_j(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) change(u<<1,l,r,x);
    if(r>mid) change(u<<1|1,l,r,x);
    pushup(u);
}
void jia(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&r>=tr[u].r)
    {
        pushdown_c(u);
        tr[u].add+=x;
        tr[u].w+=x;
        return;
    }
    pushdown_c(u);
    pushdown_j(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) jia(u<<1,l,r,x);
    if(r>mid) jia(u<<1|1,l,r,x);
    pushup(u);
}
ll query(int u,int l,int r)
{
    if(l<=tr[u].l&&r>=tr[u].r) return tr[u].w;
    pushdown_c(u);
    pushdown_j(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll w=-2e10;
    if(l<=mid) w=query(u<<1,l,r);
    if(r>mid) w=max(w,query(u<<1|1,l,r));
    return w;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        op=read();
        if(op!=3) l=read(),r=read(),x=read();
        else l=read(),r=read();
        if(op==1) change(1,l,r,x);
        else if(op==2) jia(1,l,r,x);
        else write(query(1,l,r)),putchar('\n');
    }
    return 0;
}

by _HMZ_ @ 2022-11-11 15:54:48

@LYY_yyyy 哀酱!

您的 inf 不够小,实测改成 -1e18 就能AC


by LYY_yyyy @ 2022-11-11 16:25:11

@HMZ 还是不行捏


by LYY_yyyy @ 2022-11-11 16:28:49

@HMZ 可以啦 thx


|