关于线段树的魔改

AndyC @ 2024-11-28 16:37:06

by Down_syndrome @ 2024-11-28 16:43:38

@yukimianyan？orz

by UYHW @ 2024-11-28 16:43:40

是否清醒

by __ZYX__ @ 2024-11-28 16:43:56

@Down_syndrome@In_Memory 为啥要吉司机

by AndyC @ 2024-11-28 16:44:53

@yukimianyan 细说

by AndyC @ 2024-11-28 16:47:28

兄弟们 我貌似搞出来了 大家看看对不对

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500005],sum[500005],lazy[500005],x,y,num;

void push_down(int rt,int l,int r){
    if(lazy[rt]>sum[rt]){
        int m=r+l>>1;
        sum[rt]=lazy[rt];
        lazy[rt<<1]=max(lazy[rt],lazy[rt<<1]);
        lazy[rt<<1|1]=max(lazy[rt],lazy[rt<<1|1]);
        lazy[rt]=0;
    }
} 
void push_up(int rt){
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=a[r];
        return;
    }
    int m=r+l>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    push_up(rt);
}
void update(int rt,int l,int r,int ll,int rr,int v){
    if(ll<=l&&rr>=r){
        if(v<=sum[rt]) return;
        lazy[rt]=max(lazy[rt],v);
        sum[rt]=v;
        return;
    }
    push_down(rt,l,r);
    int m=r+l>>1;
    if(ll<=m){
        update(rt<<1,l,m,ll,rr,v);
    }
    if(rr>m){
        update(rt<<1|1,m+1,r,ll,rr,v);
    }
    push_up(rt);
}
int query(int rt,int l,int r,int ll,int rr){
    if(ll<=l&&rr>=r){
        return sum[rt];
    }
    push_down(rt,l,r);
    int m=r+l>>1;
    int res=0;
    if(ll<=m) res=max(res,query(rt<<1,l,m,ll,rr));
    if(rr>m) res=max(res,query(rt<<1|1,m+1,r,ll,rr));
    return res;
}
signed main(){
    n=100;
    update(1,1,n,1,5,3);
    update(1,1,n,4,5,200);
    cout<<query(1,1,n,1,5)<<endl;
}
/*
7 3
1 2 3 4 5 6 7
1 1 7 3
1 1 3 -2
2 1 3

9

8 10
659 463 793 740 374 330 772 681 
1 5 8 39
2 5 8
1 3 6 3
1 5 8 90
1 1 5 21
2 3 8
1 3 8 17
1 4 7 52
2 2 6
1 2 7 41

2313
4281
3278

*/

by __ZYX__ @ 2024-11-28 16:47:54

@AndyC 就是你直接修改的时候就

w[u]=max(w[u],k);
lazy[u]=max(lazy[u],k);

然后 pushdown 就正常子节点取 max 就可以了啊

by Down_syndrome @ 2024-11-28 16:49:52

@ZYX 哦对哦我唐唐唐