60pts求救

P1253 扶苏的问题

wch2021 @ 2024-10-21 16:52:09

rt,前6个点能过，后4个点WA

#include<bits/stdc++.h>
#define int __int128
const int inf=1e27+1;
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!(ch>='0'&&ch<='9'))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int mx,lay,layj;
}tr[8000005];
void pu(int u)
{
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pd(int u)
{
    if(tr[u].lay!=-inf)
    {
        tr[u<<1].lay=tr[u<<1|1].lay=tr[u<<1].mx=tr[u<<1|1].mx=tr[u].lay;
        tr[u<<1].layj=tr[u<<1|1].layj=0;
        tr[u].lay=-inf;
        tr[u].layj=0;
    }
    tr[u<<1].mx+=tr[u].layj;
    tr[u<<1].layj+=tr[u].layj;
    tr[u<<1|1].mx+=tr[u].layj;
    tr[u<<1|1].layj+=tr[u].layj;
    tr[u].layj=0;
}
void build(int l,int r,int u)
{
    if(l==r)
    {
        tr[u].mx=read();
        tr[u].lay=-inf;
        return;
    }
    tr[u].mx=-inf;
    tr[u].lay=-inf;
    int mid=l+r>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pu(u);
}
void upd(int L,int R,int l,int r,int u,int x,int opt)
{
    if(L<=l&&r<=R)
    {
        if(opt==1)
        {
            tr[u].mx=x;
            tr[u].lay=x;
            tr[u].layj=0;
        }
        if(opt==2)
        {
            tr[u].mx+=x;
            if(tr[u].lay==-inf) tr[u].layj+=x;
            else tr[u].lay+=x;
        }
        return;
    }
    pd(u);
    int mid=l+r>>1;
    if(L<=mid) upd(L,R,l,mid,u<<1,x,opt);
    if(R>mid) upd(L,R,mid+1,r,u<<1|1,x,opt);
    pu(u);
}
int query(int L,int R,int l,int r,int u)
{
    if(L<=l&&r<=R) return tr[u].mx;
    pd(u);
    int mid=l+r>>1,ans=-inf;
    if(L<=mid) ans=max(ans,query(L,R,l,mid,u<<1));
    if(R>mid) ans=max(ans,query(L,R,mid+1,r,u<<1|1));
    return ans;
}
signed main()
{
//  freopen("P1253_7.in","r",stdin); 
//  freopen("P1253.out","w",stdout); 
    int n=read(),q=read();
    build(1,n,1);
    while(q--)
    {
        int opt=read(),l=read(),r=read();
        if(opt!=3) upd(l,r,1,n,1,read(),opt);
        else
        {
            write(query(l,r,1,n,1));
            putchar('\n');
        }
    }
    return 0;
}

by MutU @ 2024-10-21 17:22:30

@wch2021 两个修改：

  1. __int128 改为 long long，否则过不了，猜测是因为某个自带函数处理不了 __int128

  2. push_down 部分，在下传 lay 时不能清空当前节点的 layj。否则会覆盖掉父亲之后下传的 layj

修改后的 AC 代码：

#include<bits/stdc++.h>
#define int long long
const int inf=1e18+1;
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!(ch>='0'&&ch<='9'))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int mx,lay,layj;
}tr[8000005];
void pu(int u)
{
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pd(int u)
{
    if(tr[u].lay!=-inf)
    {
        tr[u<<1].lay=tr[u<<1|1].lay=tr[u<<1].mx=tr[u<<1|1].mx=tr[u].lay;
        tr[u<<1].layj=tr[u<<1|1].layj=0;
        tr[u].lay=-inf;
    }
    tr[u<<1].mx+=tr[u].layj;
    tr[u<<1].layj+=tr[u].layj;
    tr[u<<1|1].mx+=tr[u].layj;
    tr[u<<1|1].layj+=tr[u].layj;
    tr[u].layj=0;
}
void build(int l,int r,int u)
{
    if(l==r)
    {
        tr[u].mx=read();
        tr[u].lay=-inf;
        return;
    }
    tr[u].mx=-inf;
    tr[u].lay=-inf;
    int mid=l+r>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pu(u);
}
void upd(int L,int R,int l,int r,int u,int x,int opt)
{
    if(L<=l&&r<=R)
    {
        if(opt==1)
        {
            tr[u].mx=x;
            tr[u].lay=x;
            tr[u].layj=0;
        }
        if(opt==2)
        {
            tr[u].mx+=x;
            if(tr[u].lay==-inf) tr[u].layj+=x;
            else tr[u].lay+=x;
        }
        return;
    }
    pd(u);
    int mid=l+r>>1;
    if(L<=mid) upd(L,R,l,mid,u<<1,x,opt);
    if(R>mid) upd(L,R,mid+1,r,u<<1|1,x,opt);
    pu(u);
}
int query(int L,int R,int l,int r,int u)
{
    if(L<=l&&r<=R) return tr[u].mx;
    pd(u);
    int mid=l+r>>1,ans=-inf;
    if(L<=mid) ans=max(ans,query(L,R,l,mid,u<<1));
    if(R>mid) ans=max(ans,query(L,R,mid+1,r,u<<1|1));
    return ans;
}
signed main()
{
//  freopen("P1253_7.in","r",stdin); 
//  freopen("P1253.out","w",stdout); 
    int n=read(),q=read();
    build(1,n,1);
    while(q--)
    {
        int opt=read(),l=read(),r=read();
        if(opt!=3) upd(l,r,1,n,1,read(),opt);
        else
        {
            write(query(l,r,1,n,1));
            putchar('\n');
        }
    }
    return 0;
}

求关

by wch2021 @ 2024-10-21 17:26:05

@ghy_jerami__ 已过，感谢dalao 马上关

by MutU @ 2024-10-21 17:28:04

@wch2021 壶关了

|