首页 » 技术分享 » 吉如一线段树

吉如一线段树

　
评论关闭　968次浏览

例题

深深意识到我是一只菜鸡

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 550010
#define ll long long
#define INF 0x3f3f3f3f
struct tree{
    int l,r;
    int mx;//区间最值
    int mx_;//区间历史最值
    int se;//次大
    int cnt;
    ll sum;//区间和
    int add1,add1_,add2,add2_;//四个懒惰标记
    //add1_维护mx_. add2和add2_维护se
}t[N<<2];
int n,m,f;
int a[N];

void pushup(int p){//更新区间和，区间最大值，次大值，历史最大值
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].mx_=max(t[p*2].mx_,t[p*2+1].mx_);
    if(t[p*2].mx==t[p*2+1].mx){
        t[p].mx=t[p*2].mx;
        t[p].se=max(t[p*2].se,t[p*2+1].se);
        t[p].cnt=t[p*2].cnt+t[p*2+1].cnt;
    }
    else if(t[p*2].mx>t[p*2+1].mx){
        t[p].mx=t[p*2].mx;
        t[p].se=max(t[p*2].se,t[p*2+1].mx);
        t[p].cnt=t[p*2].cnt;
    }
    else{
        t[p].mx=t[p*2+1].mx;
        t[p].se=max(t[p*2].mx,t[p*2+1].se);
        t[p].cnt=t[p*2+1].cnt;
    }
}



void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    t[p].add1=t[p].add1_=t[p].add2=t[p].add2_=0;
    if(l==r){
        t[p].sum=t[p].mx_=t[p].mx=a[l];
        t[p].se=-INF,t[p].cnt=1;
        return ;
    }
    int mid =l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}


void update(int p,int k1,int k1_,int k2,int k2_){
    //标记下传时更新当前p的值
    //k1为区间增加标记
    //k1_为加减标记的历史最大值
    //k2为非最大值加减标记
    //k2_为非最大值历史加减标记
    t[p].sum+=1ll*k1*t[p].cnt+1ll*k2*(t[p].r-t[p].l+1-t[p].cnt);
    t[p].mx_=max(t[p].mx_,t[p].mx+k1_);//更新区间历史最大值
    t[p].add1_=max(t[p].add1_,t[p].add1+k1_);//更新标记
    t[p].mx+=k1,t[p].add1+=k1;//更新区间最大值和懒惰标记
    t[p].add2_=max(t[p].add2_,t[p].add2+k2_);//更新非最大值标记
    if(t[p].se!=-INF) t[p].se+=k2;
    t[p].add2+=k2;
}

void pushdown(int p){//标记下穿
    int temp=max(t[p*2].mx,t[p*2+1].mx);
    if(t[p*2].mx==temp)//如果左子树有最大值的话 就需要更新左子树
        update(2*p,t[p].add1,t[p].add1_,t[p].add2,t[p].add2_);
    else update(2*p,t[p].add2,t[p].add2_,t[p].add2,t[p].add2_);
    if(t[p*2+1].mx==temp)//如果右子树有最大值的话 就需要更新左子树
        update(2*p+1,t[p].add1,t[p].add1_,t[p].add2,t[p].add2_);
    else update(2*p+1,t[p].add2,t[p].add2_,t[p].add2,t[p].add2_);
    //即使没有最大值 也需要更新其他标记
    t[p].add1=t[p].add1_=t[p].add2=t[p].add2_=0;
}


void modify1(int p,int l,int r,int k){//区间加
    if(t[p].l>r||t[p].r<l) return ;
    if(l<=t[p].l&&r>=t[p].r){
        update(p,k,k,k,k);return ;//全部加上k
    }
    pushdown(p);
    modify1(2*p,l,r,k),modify1(2*p+1,l,r,k);
    pushup(p);
}


void modify2(int p,int l,int r,int k){//取min（a[i],v）;
    if(t[p].l>r||t[p].r<l||k>=t[p].mx) return ;
    if(l<=t[p].l&&r>=t[p].r&&k>t[p].se){//更新最大值
        update(p,k-t[p].mx,k-t[p].mx,0,0);return ;
    }
    pushdown(p);
    modify2(p*2,l,r,k),modify2(p*2+1,l,r,k);
    pushup(p);
}

ll query3(int p,int l,int r){//求区间和
    if(t[p].l>r||t[p].r<l) return 0;
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    pushdown(p);
    return query3(p*2,l,r)+query3(p*2+1,l,r);
}

int query4(int p,int l,int r){//求区间最大值
    if(t[p].l>r||t[p].r<l) return -INF;
    if(l<=t[p].l&&r>=t[p].r) return t[p].mx;
    pushdown(p);
    return max(query4(p*2,l,r),query4(p*2+1,l,r));
}

int query5(int p,int l,int r){//求历史最大值
    if(t[p].l>r||t[p].r<l) return -INF;
    if(l<=t[p].l&&r>=t[p].r) return t[p].mx_;
    pushdown(p);
    return max(query5(p*2,l,r),query5(p*2+1,l,r));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>f;
        int l,r,k;
        if(f==1){
            cin>>l>>r>>k;
            modify1(1,l,r,k);
        }
        else if(f==2){
            cin>>l>>r>>k;
            modify2(1,l,r,k);
        }
        else if(f==3) {
            cin>>l>>r;
            cout << query3(1, l, r) << endl;
        }
        else if(f==4) {
            cin>>l>>r;
            cout << query4(1, l, r) << endl;
        }
        else if(f==5){
            cin>>l>>r;
            cout << query5(1, l, r) << endl;
        }
    }
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：吉如一线段树，转载请注明来源！

赞 0