MnZn求调线段树板子

Jorisy @ 2022-09-11 20:37:04

by Jorisy @ 2022-09-11 20:37:11

#include<bits/stdc++.h>
#define int long long
#define lc (i<<1)
#define rc (i<<1|1)
#define mid (l+r>>1)
using namespace std;

struct node{
    int maxs,rev,add;
}sgt[8000005];
int n,q,a[1000005];

void upd(node &x,node y,node z)
{
    x.maxs=max(y.maxs,z.maxs);
}

void build(int i,int l,int r)
{
    sgt[i].maxs=LLONG_MIN;
    sgt[i].rev=LLONG_MIN;
    if(l>=r)
    {
        sgt[i].maxs=a[r];
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    upd(sgt[i],sgt[lc],sgt[rc]);
}

void pushdown_rev(int i)
{
    int x=sgt[i].rev,y=sgt[i].add;
    sgt[i].rev=LLONG_MIN;
    sgt[i].add=0;
    sgt[lc].rev=x;
    sgt[lc].add+=y;
    sgt[lc].maxs=x+y;
    sgt[rc].rev=x;
    sgt[rc].add+=y;
    sgt[rc].maxs=x+y;
}

void pushdown_add(int i)
{
    int x=sgt[i].add;
    sgt[i].add=0;
    sgt[lc].add+=x;
    sgt[lc].maxs=max(sgt[lc].maxs,sgt[lc].maxs+x);
    sgt[rc].add+=x;
    sgt[rc].maxs=max(sgt[rc].maxs,sgt[rc].maxs+x);
}

void pushdown(int i)
{
    if(sgt[i].rev!=LLONG_MIN) pushdown_rev(i);
    else if(sgt[i].add) pushdown_add(i);
}

void mdf(int i,int l,int r,int x,int y,int d,int op)
{
    if(x<=l&&r<=y)
    {
        if(op==1)
        {
            sgt[i].rev=d;
            sgt[i].maxs=d;
        }
        else
        {
            sgt[i].add+=d;
            sgt[i].maxs=max(sgt[i].maxs,sgt[i].maxs+d);
        }
        return;
    }
    pushdown(i);
    if(x<=mid) mdf(lc,l,mid,x,y,d,op);
    if(y>mid) mdf(rc,mid+1,r,x,y,d,op);
    upd(sgt[i],sgt[lc],sgt[rc]);
}

int qry(int i,int l,int r,int x,int y)
{
    //cerr<<"DEBUG: "<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<sgt[i].maxs<<endl;
    if(x<=l&&r<=y) return sgt[i].maxs;
    int res=LLONG_MIN;
    pushdown(i);
    if(x<=mid) res=max(res,qry(lc,l,mid,x,y));
    if(y>mid) res=max(res,qry(rc,mid+1,r,x,y));
    return res;
}

void debug(int i=1,int l=1,int r=n)
{
    cerr<<l<<'~'<<r<<": "<<sgt[i].maxs<<' '<<sgt[i].rev<<' '<<sgt[i].add<<endl;
    if(l>=r) return;
    debug(lc,l,mid);
    debug(rc,mid+1,r);
}

signed main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        int op,x,y,z;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op>2) printf("%lld\n",qry(1,1,n,x,y));
        else
        {
            scanf("%lld",&z);
            mdf(1,1,n,x,y,z,op);
        }
    }
    //debug();
    return 0;
}

by Azure__ @ 2022-09-11 20:42:48

@JYqwq pushdown_rev挂了

by JackMerryYoung @ 2022-09-11 20:43:28

@JYqwq 不开 ll 见祖宗。

by Jorisy @ 2022-09-11 20:43:47

@Azure__ 可以具体说一下哪儿挂了吗/kk

by Jorisy @ 2022-09-11 20:44:03

@JackMerryYoung 看看第二行是什么

by JackMerryYoung @ 2022-09-11 20:44:52

@JYqwq 欧WSSB, 还有您写的好奇怪啊。

by Azure__ @ 2022-09-11 20:46:18

lz写的真怪，我刚刚搞错了

by Azure__ @ 2022-09-11 20:48:35

sgt[rc].add=sgt[lc].add=0;
sgt[rc].maxs=sgt[lc].maxs=x;

by Azure__ @ 2022-09-11 20:48:49

@JYqwq

by Jorisy @ 2022-09-11 20:52:01

@Azure__ 改了后还是50pts..