MnZn求调线段树板子

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

by JackMerryYoung @ 2022-09-11 20:56:33

改对了：

#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[4000005];
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[l];
        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;
    sgt[i].rev=LLONG_MIN;
    sgt[lc].rev=x;
    sgt[lc].add=0;
    sgt[lc].maxs=x;
    sgt[rc].rev=x;
    sgt[rc].add=0;
    sgt[rc].maxs=x;
}

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

void pushdown(int i)
{
    if(sgt[i].rev!=LLONG_MIN) pushdown_rev(i);
    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].add=0;
            sgt[i].rev=d;
            sgt[i].maxs=d;
        }
        else
        {
            sgt[i].add+=d;
            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 JackMerryYoung @ 2022-09-11 20:56:42

@JYqwq

by Azure__ @ 2022-09-11 20:57:47

@JYqwq

sgt[rc].maxs=max(sgt[rc].maxs,sgt[rc].maxs+x);
改成：
sgt[rc].maxs=+=x;
另一个同理

by Azure__ @ 2022-09-11 20:58:29

唔，看来我慢了1min

by Jorisy @ 2022-09-11 21:04:12

@JackMerryYoung @Azure__ 感谢 /bx