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

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 Star0230 @ 2024-07-17 21:48:54

e，这是啥，我才学到dp

by cqbzpyl @ 2024-07-17 21:59:36

emmm
说实话，我啥也没看懂（无恶意）

内个 pushdown() 函数是真没看懂

发个模版吧

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int l,r;
    int add,sum,maxn;
}t[1000010];
int a[1000010]; 
void build(int p,int l,int r){//建树 
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return;
    } 
    int tm=l+(r-l)>>1;
    build(p<<1,l,tm);
    build(p<<1|1,tm+1,r);

    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void update(int p,int x,int v){//单点修改 
    if(t[p].l==t[p].r){
        t[p].sum=x;
        return;
    }
    int tm=t[p].l+(t[p].r-t[p].l)>>1;
    if(x<=tm) build(p<<1,x,v);
    else build(p<<1|1,x,v);

    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;//push_up
}
int query(int p,int l,int r){//区间最值查询 
    if(l<=t[p].l&&t[p].r<=r)
        return t[p].maxn;
    int tm=(t[p].l+t[p].r)>>1;
    int val=-(1<<30);
    if(l<=tm)
        val=max(val,query(p<<1,l,r));
    if(r>tm)
        val=max(val,query(p<<1|1,l,r));
    return val;
}
void spread(int p){//Lasy_tag
    if(t[p].add){
        t[p<<1].sum+=t[p].add*(t[p<<1].r-t[p<<1].l+1);
        t[p<<1|1].sum+=t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1);
        t[p<<1].add+=t[p].add;
        t[p<<1|1].add+=t[p].add;
        t[p].add=0;
    }                      
}
void change(int p,int l,int r,int d){//区间修改 
    if(l<=t[p].l&&t[p].r<=r){
        t[p].sum+=d*(t[p].r-t[p].l+1);
        t[p].add+=d;
        return;
    }
    spread(d);
    int tm=t[p].l+(t[p].r-t[p].l)>>1;
    if(l<=tm)
        change(p<<1,l,r,d);
    if(r>tm)
        change(p<<1|1,l,r,d);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
int find(int p,int l,int r){//区间查询 
    if(l<=t[p].l&&t[p].r<=r)
        return t[p].sum;
    spread(p);
    int val=0;
    int tm=t[p].l+(t[p].r-t[p].l)>>1;
    if(l<=tm)
        val+=find(p<<1,l,r);
    if(tm<r)
        val+=find(p<<1|1,l,r);
    return val;
}
signed main() {

    return 0;
}

求关

by cqbzpyl @ 2024-07-17 22:01:12

虽然但是，这写的是啥呀（无恶意）

by cqbzpyl @ 2024-07-17 22:03:31

@cqbzpyl 没勾选手瑟瑟发抖

by mm1215_1 @ 2024-07-18 12:13:24

update(pushup)里p.gai=p.mx; 似乎有问题

by mm1215_1 @ 2024-07-18 12:51:53

@mm1215_1 @Eternality

将这句话去掉20pts

by mm1215_1 @ 2024-07-18 12:52:25

你不应该在pushup上传里修改lzay tag

by mm1215_1 @ 2024-07-18 13:13:12

@Eternality

我帮你改了下，到50pts了，但是我没时间了，要不你自己再调下

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

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;

}

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));
        }
    }
    return 0;
}

by mm1215_1 @ 2024-07-18 16:51:40

@Eternality 感觉你线段树很多错误，有些还表现出你没有真正理解线段树，建议重学。我明天有时间帮你调

by steveyang137 @ 2024-07-20 10:53:34

@mm1215_1 猜一手inf小了，改1e18试试