呜呜呜一年半之后复习，连线段树都不会写了，求大佬调

Eternality @ 2024-07-17 21:38:10

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n,q,a[N];

struct T
{
    int l,r,mx,gai,jia;
}t[4*N];

T update(T &p,T ls,T rs)
{
    p.mx=max(ls.mx,rs.mx);
    p.gai=p.mx;
    return p;
}

void tag(int p,int op,int x)
{
    if(op==1)
    {
        t[p].gai=x;
    }
    if(op==2)
    {
        t[p].jia+=x;
    }
}

void pushdown(int p)
{
    t[p<<1].mx=t[p].gai;
    t[p<<1].mx+=t[p].jia;
    t[p<<1|1].mx=t[p].gai;
    t[p<<1|1].mx+=t[p].jia;
    t[p<<1].gai=t[p].gai;
    t[p<<1].jia+=t[p].jia;
    t[p<<1|1].gai=t[p].gai;
    t[p<<1|1].jia+=t[p].jia;
    t[p].jia=0;
}

void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r)
    {
        t[p].mx=a[l];
        t[p].gai=t[p].mx;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    update(t[p],t[p<<1],t[p<<1|1]);
}

void change(int p,int l,int r,int x)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].mx=x;
        tag(p,1,x);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)change(p<<1,l,r,x);
    if(r>=mid+1)change(p<<1|1,l,r,x);
    update(t[p],t[p<<1],t[p<<1|1]);
}

void add(int p,int l,int r,int x)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].mx+=x;
        tag(p,2,x);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)add(p<<1,l,r,x);
    if(r>mid)add(p<<1|1,l,r,x);
    update(t[p],t[p<<1],t[p<<1|1]);
}

T ask(int p,int l,int r)
{
//  if(t[p].l==t[p].r)return t[p];
    if(l<=t[p].l&&r>=t[p].r)return t[p];
    pushdown(p);
    T ans;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>=mid+1)return update(ans,ask(p<<1,l,r),ask(p<<1|1,l,r));
    if(r<=mid)return ask(p<<1,l,r);
    if(l>=mid+1)return ask(p<<1|1,l,r);
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
//  for(int i=1;i<=11;i++)
//  {
//      cout<<t[i].l<<"   "<<t[i].r<<"   "<<t[i].mx<<"   "<<endl;
//   } 
    while(q--)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            int x;
            scanf("%d",&x);
            change(1,l,r,x);
        }else if(op==2)
        {
            int x;
            scanf("%d",&x);
            add(1,l,r,x);
        }else
        {
            printf("%d\n",ask(1,l,r).mx);
        }
    }
    return 0;
}

by mm1215_1 @ 2024-07-20 17:37:15

ll后60pts

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e6+10 , inf = 2e18;

int n,q,a[N];

struct T

{

    int l,r,mx,gai,jia;

}t[4*N];

T update(T &p,T ls,T rs)

{

    p.mx=max(ls.mx,rs.mx);

    return p;

}

void tag(int p,int op,int x)

{

    if(op==1)

    {

        t[p].gai=x;

    }

    if(op==2)

    {

        t[p].jia+=x;

    }

}

void pushdown(int p)

{

    if (t[p].gai != inf) t[p<<1].mx=t[p].gai;

    t[p<<1].mx+=t[p].jia;

    if (t[p].gai != inf) t[p<<1|1].mx=t[p].gai;

    t[p<<1|1].mx+=t[p].jia;

    if (t[p].gai != inf) t[p<<1].gai=t[p].gai;

    t[p<<1].jia+=t[p].jia;

    if (t[p].gai != inf) t[p<<1|1].gai=t[p].gai;

    t[p<<1|1].jia+=t[p].jia;

    t[p].jia=0; t[p].gai = inf;

}

void build(int p,int l,int r)

{

    t[p].gai = inf;

    t[p].l=l;

    t[p].r=r;

    if(l==r)

    {

        t[p].mx=a[l];

        return;

    }

    int mid=l+r>>1;

    build(p<<1,l,mid);

    build(p<<1|1,mid+1,r);

    update(t[p],t[p<<1],t[p<<1|1]);

}

void change(int p,int l,int r,int x)

{

    if(l<=t[p].l&&r>=t[p].r)

    {

        t[p].mx=x;

        tag(p,1,x);

        return;

    }

    pushdown(p);

    int mid=t[p].l+t[p].r>>1;

    if(l <= mid)change(p<<1,l,r,x);

    if(r > mid)change(p<<1|1,l,r,x);

    update(t[p],t[p<<1],t[p<<1|1]);

}

void add(int p,int l,int r,int x)

{

    if(l<=t[p].l&&r>=t[p].r)

    {

        t[p].mx+=x;

        tag(p,2,x);

        return;

    }

    pushdown(p);

    int mid=t[p].l+t[p].r>>1;

    if(l <= mid)add(p<<1,l,r,x);

    if(r > mid)add(p<<1|1,l,r,x);

    update(t[p],t[p<<1],t[p<<1|1]);

}

int ask(int p,int l,int r)

{

//  if(t[p].l==t[p].r)return t[p];

    if(l<=t[p].l&&r>=t[p].r)return t[p].mx;

    pushdown(p);

    int mid=t[p].l+t[p].r>>1 , ans = -inf;

    if(l <= mid) ans = max(ans , ask(p<<1,l,r));

    if(r > mid) ans = max(ans , ask(p<<1|1,l,r));

    return ans;

}

signed main()

{

    scanf("%lld%lld",&n,&q);

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

    build(1,1,n);

//  for(int i=1;i<=11;i++)

//  {

//      cout<<t[i].l<<"   "<<t[i].r<<"   "<<t[i].mx<<"   "<<endl;

//   } 

    while(q--)

    {

        int op,l,r;

        scanf("%lld%lld%lld",&op,&l,&r);

        if(op==1)

        {

            int x;

            scanf("%lld",&x);

            change(1,l,r,x);

        }else if(op==2)

        {

            int x;

            scanf("%lld",&x);

            add(1,l,r,x);

        }else

        {

            printf("%lld\n",ask(1,l,r));

        }

    }

    return 0;

}

by Eternality @ 2024-07-29 14:55:13

@mm1215_1 噢噢，谢谢

by lemoned_qwq @ 2024-08-18 12:32:54

@Eternality What is "线段树"?