60pts求调

firstlight @ 2023-08-17 23:28:37

// Problem: P1253 扶苏的问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1253
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll INF=1e20;

int n,q;
int w[N];
struct Node{
    int l,r;
    ll Max,f1,f2;
}tr[N*4];

void pushup(int u)
{
    tr[u].Max=max(tr[u<<1].Max,tr[u<<1|1].Max);
}

void pushdown(int u)
{
    if(tr[u].f1!=INF)
    {
        tr[u].f2=tr[u<<1].f2=tr[u<<1|1].f2=0;
        tr[u<<1].f1=tr[u].f1;
        tr[u<<1].Max=tr[u].f1;
        tr[u<<1|1].f1=tr[u].f1;
        tr[u<<1|1].Max=tr[u].f1;
        tr[u].f1=INF;
    }
    else
    {
        tr[u<<1].f2+=tr[u].f2;
        tr[u<<1].Max+=tr[u].f2;
        tr[u<<1|1].f2+=tr[u].f2;
        tr[u<<1|1].Max+=tr[u].f2;
        tr[u].f2=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,w[r],INF,0};
    else 
    {
        tr[u]={l,r,0,INF,0};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,ll f,ll a)
{
    Node &ro=tr[u];
    if(ro.l>=l&&ro.r<=r)
    {
        if(f!=INF)
        {
            ro.Max=f;
            tr[u].f1=f;
        }
        else
        {
            ro.Max+=a;
            ro.f2+=a;
        }
    }
    else 
    {
        pushdown(u);
        int mid=ro.l+ro.r>>1;
        if(l<=mid) modify(u<<1,l,r,f,a);
        if(r>mid) modify(u<<1|1,l,r,f,a);
        pushup(u);
    }
}

ll query(int u,int l,int r)
{
    Node &ro=tr[u]; 
    if(ro.l>=l&&ro.r<=r) return tr[u].Max;
    ll res = -INF;
    pushdown(u);
    int mid=ro.l+ro.r>>1;
    if(l<=mid) res = max(res, query(u<<1,l,r));
    if(r>mid) res = max(res, query(u<<1|1,l,r));
    return res;
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);
    for(int i = 1; i <= n; i ++)  query(1, i, i);
    int op,l,r,x;
    while(q--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            scanf("%d",&x);
            modify(1,l,r,x,0);
        }
        else if(op==2)
        {
            scanf("%d",&x);
            modify(1,l,r,INF,x);
        }
        else printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by firstlight @ 2023-08-17 23:29:26

已经调了一晚上了，救救孩子吧！

by TimeLimitEnough @ 2023-08-18 08:52:26

@firstlight pushdown错了，f1和f2是可以同时存在的，比如你先区间赋1，在区间+2，那最后的结果就是区间的值全为3

by firstlight @ 2023-08-18 09:45:22

感谢大佬

by firstlight @ 2023-08-18 09:56:13

@TimeLimitEnough

// Ptr[u]blem: P1253 扶苏的问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/ptr[u]blem/P1253
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000010;
const ll INF=1e18;

int n,q;
int w[N];
struct Node{
    int l,r;
    ll Max,f1,f2;
}tr[N*4];

void pushup(int u)
{
    tr[u].Max=max(tr[u<<1].Max,tr[u<<1|1].Max);
}

void pushdown(int u)
{
    if(tr[u].f1 < INF)
    {
        tr[u<<1].f1=tr[u].f1;
        tr[u<<1].Max=tr[u].f1;
        tr[u<<1|1].f1=tr[u].f1;
        tr[u<<1|1].Max=tr[u].f1;
        tr[u].f1=INF;
    }
    else if(tr[u].f2)
    {
        if (tr[u<<1].f1 != INF)
            tr[u<<1].f1+=tr[u].f2;
        else tr[u<<1].f2+=tr[u].f2;
        tr[u<<1].Max+=tr[u].f2;
        if (tr[u<<1|1].f1 != INF)
            tr[u<<1|1].f1 += tr[u].f2;
        else tr[u<<1|1].f2+=tr[u].f2;
        tr[u<<1|1].Max+=tr[u].f2;
        tr[u].f2=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,w[r],INF,0};
    else 
    {
        tr[u]={l,r,0,INF,0};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,ll f,ll a)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        if(f!=INF)
        {
            tr[u].Max=f;
            tr[u].f1=f;
            tr[u].f2=0;
        }
        else
        {
            if (tr[u].f1 != INF)
            {
                tr[u].f1 += a;
                tr[u].Max+=a;
            }
            else
            {
                tr[u].Max+=a;
                tr[u].f2+=a;
            }
        }
    }
    else 
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,f,a);
        if(r>mid) modify(u<<1|1,l,r,f,a);
        pushup(u);
    }
}

ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Max;
    ll res = -INF;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) res = max(res, query(u<<1,l,r));
    if(r>mid) res = max(res, query(u<<1|1,l,r));
    return res;
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);
    int op,l,r,x;
    while(q--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            scanf("%d",&x);
            modify(1,l,r,x,0);
        }
        else if(op==2)
        {
            scanf("%d",&x);
            modify(1,l,r,INF,x);
        }
        else
        {
            printf("%lld\n",query(1,l,r));
            // for(int i=1;i<=n;i++) printf("%lld ",query(1,i,i));
            // printf("\n");
        } 
        // for(int i=1;i<=80;i++) printf("%d %d %lld %lld %lld\n",tr[i].l, tr[i].r, tr[i].f2, tr[i].Max, tr[i].f1);
        // printf("\n");
    }
    return 0;
}

by firstlight @ 2023-08-18 09:56:47

改成这样？

by firstlight @ 2023-08-18 09:57:35

似乎还不行