线段树20pts求调

tai_chi @ 2022-10-06 10:24:50

by tai_chi @ 2022-10-06 10:24:58

马蜂自以为还行

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5,inf=1e15+7;
struct node{
    int l,r,w,tag1,tag2;
    //w是最大值，tag1是赋值，tag2是增加 
}t[4*maxn];
int n,q;
int a[maxn];
void pushup(int u)
{
    t[u].w=max(t[u*2].w,t[u*2+1].w);
}
void build(int u,int l,int r)
{
    t[u].l=l;t[u].r=r;t[u].tag1=inf;
    if(l==r)
    {
        t[u].w=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
void maketag1(int u,int x)
{
    t[u].tag1=x;t[u].tag2=0;
    t[u].w=x;
}
void maketag2(int u,int x)
{
    t[u].tag2=x;
    t[u].w+=x;
}
void pushdown(int u)
{
    if(t[u].tag1!=inf)
    {
        maketag1(u*2,t[u].tag1);
        maketag1(u*2+1,t[u].tag1);
    }
    else
    {
        maketag2(u*2,t[u].tag2);
        maketag2(u*2+1,t[u].tag2);
    }
    t[u].tag1=inf;t[u].tag2=0;
}
bool inrange(int l,int r,int L,int R){return ((L<=l)&&(r<=R));}
bool outofrange(int l,int r,int L,int R){return ((R<l)||(r<L));}
void change(int u,int L,int R,int x)
{
    //cout<<t[u].l<<" "<<t[u].r<<" ";
    if(inrange(t[u].l,t[u].r,L,R))
    {
        //cout<<"in\n";
        maketag1(u,x);
        return;
    }
    else if(!outofrange(t[u].l,t[u].r,L,R))
    {
        //cout<<"part\n";
        pushdown(u);
        change(u*2,L,R,x);
        change(u*2+1,L,R,x);
        pushup(u);
        return;
    }
    //cout<<"out\n";
    return;
}
void add(int u,int L,int R,int x)
{
    if(inrange(t[u].l,t[u].r,L,R))
    {
        maketag2(u,x);
        return;
    }
    else if(!outofrange(t[u].l,t[u].r,L,R))
    {
        pushdown(u);
        add(u*2,L,R,x);
        add(u*2+1,L,R,x);
        pushup(u);
        return;
    }
    return;
}
int ask(int u,int L,int R)
{
    if(inrange(t[u].l,t[u].r,L,R))
    {
        return t[u].w;
    }
    else if(!outofrange(t[u].l,t[u].r,L,R))
    {
        pushdown(u);
        return max(ask(u*2,L,R),ask(u*2+1,L,R));
    }
    return -inf;
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,x;
        cin>>opt>>l>>r;
        if(opt==1)
        {
            cin>>x;
            change(1,l,r,x);
        }
        else if(opt==2)
        {
            cin>>x;
            add(1,l,r,x);
        }
        else if(opt==3)
        {
            cout<<ask(1,l,r)<<endl;
        }
    }
    return 0;
}

by tai_chi @ 2022-10-06 10:30:21

悬赏私信，￥也不是不行

by tai_chi @ 2022-10-06 10:35:02

maketag2 漏了个加号，现在 60pts

by tai_chi @ 2022-10-06 10:39:57

过了，maketag2 还要特判有没有 tag1 存在。

发现这个帖子只有我一个sb在自娱自乐

by tai_chi @ 2022-10-06 10:40:33

void maketag2(int u,int x)
{
    t[u].w+=x;
    if(t[u].tag1==inf)
        t[u].tag2+=x;
    else
        t[u].tag1+=x;
}