萌新学了\dfrac{1}{0x66ccff}天求调线段树

P1253 扶苏的问题

Vsinger_洛天依 @ 2023-10-27 15:36:48

萌新学了\dfrac{1}{0x66ccff}天求调线段树 rt,只有40分

#include<bits/stdc++.h>
using namespace std;
int n,m,a[0x66ccff];
struct node{
    long long l,r;
    long long lazy,dat,lazyy;
}t[0x66ccff];
inline void build(int q,int l,int r){
    t[q].l=l;
    t[q].r=r;
    if(l==r){
        t[q].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(q*2,l,mid);
    build(q*2+1,mid+1,r);
    t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline void lazy(int q){
    if(!t[q].lazyy){
        t[q*2].lazy+=t[q].lazy;
        t[q*2].dat+=t[q].lazy;
        t[q*2+1].lazy+=t[q].lazy;
        t[q*2+1].dat+=t[q].lazy;
        t[q].lazy=0;
    }
    else{
        t[q*2].lazy=t[q].lazy;
        t[q*2].dat=t[q].lazy;
        t[q*2+1].lazy=t[q].lazy;
        t[q*2+1].dat=t[q].lazy;
        t[q*2].lazyy=1;
        t[q*2+1].lazyy=1;
        t[q].lazyy=0;
        t[q].lazy=0;
    }

}
inline void change1(int q,int l,int r,int v)
{
    if(t[q].l>r||t[q].r<l) return;
    if(t[q].l>=l&&t[q].r<=r){
        t[q].lazy=v;
        t[q].lazyy=1;
        t[q].dat+=v;
        return;
    }
    if(t[q].lazy!=0) 
        lazy(q);
    change1(q*2,l,r,v);
    change1(q*2+1,l,r,v);
    t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline void change(int q,int l,int r,int v)
{
    if(t[q].l>r || t[q].r<l) return;
    if(t[q].l>=l && t[q].r<=r)
    {
        t[q].lazy+=v;
        t[q].dat+=v;
        return;
    }
    if(t[q].lazy>0) 
        lazy(q);
    change(q*2,l,r,v);
    change(q*2+1,l,r,v);
    t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline long long ask(int q,int l,int r){
    if(t[q].l>r || t[q].r<l) 
        return 0;
    if(t[q].l>=l && t[q].r<=r) 
        return t[q].dat;
    if(t[q].lazy!=0) 
        lazy(q);
    return max(ask(q*2,l,r),ask(q*2+1,l,r)); 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        long long qwq,x,y,k;
        cin>>qwq;
        if(qwq==1){
            cin>>x>>y>>k;
            change1(1,x,y,k);
        }
        else if(qwq==2){
            cin>>x>>y>>k;
            change(1,x,y,k);
        }
        else {
            cin>>x>>y;
            cout<<ask(1,x,y)<<endl;
        }
    }
}

怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。 怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。


by Vsinger_洛天依 @ 2023-10-27 15:39:59

我去原来是我多打了个+此贴结

线段树change再也不直接复制写完的了

by Deuteron @ 2023-10-27 16:21:25

66ccff/se


|