样例不过求调!!!!

P1253 扶苏的问题

goodluck_hao_2007 @ 2022-10-05 22:13:07

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N=1e6+10,INF=1e9+5000000;

struct Node
{
    long long l,r;
    long long maxn;
    long long add,com;
}tr[N*4];

long long n,m;
long long w[N];

void pushup(long long u)
{
    tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
    tr[u].com=max(tr[u<<1].com,tr[u<<1|1].com);
    tr[u].maxn=max(tr[u].maxn,tr[u].com);
}

void pushdown(long long u)
{
    tr[u].maxn=max(tr[u].maxn,tr[u].com);
    tr[u<<1].maxn+=tr[u].add;
    tr[u<<1|1].maxn+=tr[u].add;
    tr[u<<1].maxn=max(tr[u].maxn,tr[u<<1].maxn);
    tr[u<<1|1].maxn=max(tr[u].maxn,tr[u<<1|1].maxn);
    tr[u].add=0;
    tr[u].com=0;
}

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

void modify1(long long u,long long l,long long r,long long add)
{
    if(tr[u].l>=l&&tr[u].r<=r) tr[u].add+=add;
    else
    {
        pushdown(u);

        long long mid=(tr[u].l+tr[u].r)>>1;
        if(mid>=l) modify1(u<<1,l,r,add);
        if(mid<r) modify1(u<<1|1,l,r,add);

        pushup(u);
    }
}

void modify2(long long u,long long l,long long r,long long com)
{
    if(tr[u].l>=l&&tr[u].r<=r) tr[u].com=com;
    else
    {
        pushdown(u);

        long long mid=(tr[u].l+tr[u].r)>>1;
        if(mid>=l) modify2(u<<1,l,r,com);
        if(mid<r) modify2(u<<1|1,l,r,com);

        pushup(u);
    }
}

long long query(long long u,long long l,long long r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxn;

    pushdown(u);
    long long num=-INF;
    long long mid=(tr[u].l+tr[u].r)>>1;
    if(mid>=l) num=max(num,query(u<<1,l,r));
    if(mid<r) num=max(num,query(u<<1|1,l,r));

    return num;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++) scanf("%lld",&w[i]);

    build(1,1,n); 

    for(int i=0;i<m;i++)
    {
        int op,l,r,x;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&l,&r,&x);
            modify1(1,l,r,x);
        }
        else if(op==2)
        {
            scanf("%d%d%d",&l,&r,&x);
            modify2(1,l,r,x);
        }
        else if(op==3)
        {
            printf("%lld\n",query(1,l,r));
        }
    }

    return 0;
}

by int_jab @ 2022-10-05 22:26:18

for(int i=0;i<n;i++) scanf("%lld",&w[i]);
build(1,1,n);

这不对吧? 应该是

for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
build(1,1,n);

by int_jab @ 2022-10-05 22:27:19

......


by cjwdxfblzs @ 2022-10-05 23:50:17

我才发现咱俩调的是一道题……


by cjwdxfblzs @ 2022-10-05 23:50:52

不过UKE先生已经给您解答了


|