吉司机线段树

详解

www.luogu.com.cn

多个例题

www.luogu.com.cn

题型：区间最值笼统地指求区间的最值以及区间所有数对 x 取最值（即令 \(a_i​=\max/\min(a_i​,x)\)）这一类的查询与修改操作。

例题 #1 HDU5306 Gorgeous Sequence

维护一个序列 a：

• 0 l r t \(\forall l\le i\le r,\ a_i=\min(a_i,t)\)。

• 1 l r 输出区间 [l,r] 中的最大值。

• 2 l r 输出区间和。

• 多组数据，\(T\le 100,n\le 10^6,\sum m\le 10^6\)。

引用自 OI wiki

区间取 min，意味着只对那些大于 t 的数有更改。因此这个操作的对象不再是整个区间，而是「这个区间中大于 t 的数」。于是我们可以有这样的思路：

每个结点维护该区间的最大值 Mx1、次大值 Mx2、区间和 Sum 以及最大值的个数 Cnt。接下来我们考虑区间对 t 取 \min 的操作。 如果 \(Mx1\le t\)，显然这个 t 是没有意义的，直接返回； 如果 \(Mx2<t\le Mx1\)，那么这个 t 就能更新当前区间中的最大值。于是我们让区间和加上 Cnt(t-Mx1)，然后更新 Mx1 为 t，并打一个标记。 如果 \(t\le Mx2\)，那么这时你发现你不知道有多少个数涉及到更新的问题。于是我们的策略就是，暴力递归向下操作。然后上传信息。

例题 #2 线段树 3

给出一个长度为 \(n\) 的数列 \(A\)，同时定义一个辅助数组 \(B\)，\(B\) 开始与 \(A\) 完全相同。接下来进行了 \(m\) 次操作，操作有五种类型，按以下格式给出：

• 1 l r k：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 加上 \(k\)（\(k\) 可以为负数）。

• 2 l r v：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 变成 \(\min(A_i,v)\)。

• 3 l r：求 \(\sum_{i=l}^{r}A_i\)。

• 4 l r：对于所有的 \(i\in[l,r]\)，求 \(A_i\) 的最大值。

• 5 l r：对于所有的 \(i\in[l,r]\)，求 \(B_i\) 的最大值。

在每一次操作后，我们都进行一次更新，让 \(B_i\gets\max(B_i,A_i)\)。

• 对于全部测试数据，保证 \(1\leq n,m\leq 5\times 10^5\)，\(-5\times10^8\leq A_i\leq 5\times10^8\)，\(op\in[1,5]\)，\(1 \leq l\leq r \leq n\)，\(-2000\leq k\leq 2000\)，\(-5\times10^8\leq v\leq 5\times10^8\)。

提示

本题输入量较大，请使用合理高效的读入方法。

代码分析

数据

struct node{
    int mx1a,cnt,mx2a,sum,mx1b;//a的最大值，a的最大值的个数，a的次大值，区间和，b的最大值
    int tg1,tg2,tg3,tg4;//4个tag分别是对应mx1a,mx2a,tg1的max,t2的max
}t[N<<2];

难点：tag对值的更新

void tagModify(int t1,int t2,int t3,int t4,int x,int l,int r){
    t[x].sum+=t1*t[x].cnt+t2*(r-l+1-t[x].cnt);
    t[x].mx1b=max(t[x].mx1b,t[x].mx1a+t3);
    t[x].mx1a+=t1;

    if(t[x].mx2a!=-INF)t[x].mx2a+=t2;


    t[x].tg3=max(t[x].tg1+t3,t[x].tg3);
    t[x].tg4=max(t[x].tg2+t4,t[x].tg4);
    t[x].tg1+=t1;t[x].tg2+=t2;
}

难点：两种操作

• 区间加操作

线段树框架就省略了，我们只看当找到了要修改的节点时对节点的修改

void tagAdd(int x,int v,int l,int r){
    t[x].sum+=v*t[x].cnt+v*(r-l+1-t[x].cnt);
    t[x].mx1a+=v;
    t[x].mx1b=max(t[x].mx1b,t[x].mx1a);
    if(t[x].mx2a!=-INF)t[x].mx2a+=v;

    t[x].tg1+=v;t[x].tg2+=v;
    t[x].tg3=max(t[x].tg1,t[x].tg3);
    t[x].tg4=max(t[x].tg2,t[x].tg4);
}

• 区间min修改操作

注意因为吉司机的特殊性，所以我们需要多一些约束条件。

void changeMin(int x,int l,int r,int pl,int pr,int v){
    if(pl>r||pr<l||v>=t[x].mx1a)return ;//注意多了条件！！！
    if(l>=pl&&r<=pr&&t[x].mx2a<v){//注意多了条件！！！
        tagMin(x,v);
        return ;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    changeMin(x<<1,l,mid,pl,pr,v);
    changeMin(x<<1|1,mid+1,r,pl,pr,v);
    pushup(x);
}

难度：pushdown标记下传操作

void pushdown(int x,int l,int r){
    int mid=l+r>>1;

    int mx=max(t[x<<1].mx1a,t[x<<1|1].mx1a);
    if(t[x<<1].mx1a==mx)tagModify(t[x].tg1,t[x].tg2,t[x].tg3,t[x].tg4,x<<1,l,mid);
    else tagModify(t[x].tg2,t[x].tg2,t[x].tg4,t[x].tg4,x<<1,l,mid);

    if(t[x<<1|1].mx1a==mx)tagModify(t[x].tg1,t[x].tg2,t[x].tg3,t[x].tg4,x<<1|1,mid+1,r);
    else tagModify(t[x].tg2,t[x].tg2,t[x].tg4,t[x].tg4,x<<1|1,mid+1,r);

    //清空tag
    t[x].tg1=t[x].tg2=t[x].tg3=t[x].tg4=0;
}

Code AC

/*
CB Ntsc
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair

const int N = 1e6 + 5;
const int M = 16;
const int INF = 2e9 + 5;
const int MOD = 9999973;


#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

bool f1;
int tr[N<<2],a[N],pos[N];
int q, n, m, ans, T;
bool f2;

struct node{
    int mx1a,cnt,mx2a,sum,mx1b;
    int tg1,tg2,tg3,tg4;//4个tag分别是对应mx1a,mx2a
}t[N<<2];


//标记传递

void pushup(int x){
    //维护最大值，区间和
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
    t[x].mx1a=max(t[x<<1].mx1a,t[x<<1|1].mx1a);
    t[x].mx1b=max(t[x<<1].mx1b,t[x<<1|1].mx1b);
    //维护次大值及最大值的个数
    if(t[x<<1].mx1a==t[x<<1|1].mx1a){
        t[x].cnt=t[x<<1].cnt+t[x<<1|1].cnt;
        t[x].mx2a=max(t[x<<1].mx2a,t[x<<1|1].mx2a);
    }else if(t[x<<1].mx1a>t[x<<1|1].mx1a){
        t[x].cnt=t[x<<1].cnt;
        t[x].mx2a=max(t[x<<1].mx2a,t[x<<1|1].mx1a);
    }else{
        t[x].cnt=t[x<<1|1].cnt;
        t[x].mx2a=max(t[x<<1].mx1a,t[x<<1|1].mx2a);
    }
}

void tagModify(int t1,int t2,int t3,int t4,int x,int l,int r){
    t[x].sum+=t1*t[x].cnt+t2*(r-l+1-t[x].cnt);
    t[x].mx1b=max(t[x].mx1b,t[x].mx1a+t3);
    t[x].mx1a+=t1;

    if(t[x].mx2a!=-INF)t[x].mx2a+=t2;


    t[x].tg3=max(t[x].tg1+t3,t[x].tg3);
    t[x].tg4=max(t[x].tg2+t4,t[x].tg4);
    t[x].tg1+=t1;t[x].tg2+=t2;
}


void pushdown(int x,int l,int r){
    int mid=l+r>>1;

    int mx=max(t[x<<1].mx1a,t[x<<1|1].mx1a);
    if(t[x<<1].mx1a==mx)tagModify(t[x].tg1,t[x].tg2,t[x].tg3,t[x].tg4,x<<1,l,mid);
    else tagModify(t[x].tg2,t[x].tg2,t[x].tg4,t[x].tg4,x<<1,l,mid);

    if(t[x<<1|1].mx1a==mx)tagModify(t[x].tg1,t[x].tg2,t[x].tg3,t[x].tg4,x<<1|1,mid+1,r);
    else tagModify(t[x].tg2,t[x].tg2,t[x].tg4,t[x].tg4,x<<1|1,mid+1,r);

    //清空tag
    t[x].tg1=t[x].tg2=t[x].tg3=t[x].tg4=0;
}

//初始化

void build(int x,int l,int r){
    if(l==r){
        t[x].sum=t[x].mx1a=t[x].mx1b=a[l];
        t[x].cnt=1;
        t[x].mx2a=-INF;
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);

    pushup(x);

}

//修改部分

void tagAdd(int x,int v,int l,int r){
    t[x].sum+=v*t[x].cnt+v*(r-l+1-t[x].cnt);
    t[x].mx1a+=v;
    t[x].mx1b=max(t[x].mx1b,t[x].mx1a);
    if(t[x].mx2a!=-INF)t[x].mx2a+=v;

    t[x].tg1+=v;t[x].tg2+=v;
    t[x].tg3=max(t[x].tg1,t[x].tg3);
    t[x].tg4=max(t[x].tg2,t[x].tg4);
}

void changeAdd(int x,int l,int r,int pl,int pr,int v){
    if(pl>r||pr<l)return ;
    if(l>=pl&&r<=pr){
        tagAdd(x,v,l,r);
        return ;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    changeAdd(x<<1,l,mid,pl,pr,v);
    changeAdd(x<<1|1,mid+1,r,pl,pr,v);
    pushup(x);

}

void tagMin(int x,int v){
    int tmp=t[x].mx1a-v;
    t[x].sum-=t[x].cnt*tmp;
    t[x].mx1a=v;
    t[x].tg1-=tmp;
}

void changeMin(int x,int l,int r,int pl,int pr,int v){
    if(pl>r||pr<l||v>=t[x].mx1a)return ;//注意多了条件！！！
    if(l>=pl&&r<=pr&&t[x].mx2a<v){//注意多了条件！！！
        tagMin(x,v);
        return ;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    changeMin(x<<1,l,mid,pl,pr,v);
    changeMin(x<<1|1,mid+1,r,pl,pr,v);
    pushup(x);
}

//查询部分

int querySum(int x,int l,int r,int pl,int pr){
    if(pl>r||pr<l)return 0;
    if(l>=pl&&r<=pr)return t[x].sum;
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return querySum(x<<1,l,mid,pl,pr)+querySum(x<<1|1,mid+1,r,pl,pr);
}

int queryMaxA(int x,int l,int r,int pl,int pr){
    if(pl>r||pr<l)return -INF;
    if(l>=pl&&r<=pr)return t[x].mx1a;
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return max(queryMaxA(x<<1,l,mid,pl,pr),queryMaxA(x<<1|1,mid+1,r,pl,pr));
}


int queryMaxB(int x,int l,int r,int pl,int pr){
    if(pl>r||pr<l)return -INF;
    if(l>=pl&&r<=pr)return t[x].mx1b;
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return max(queryMaxB(x<<1,l,mid,pl,pr),queryMaxB(x<<1|1,mid+1,r,pl,pr));
}

// void updateB(int x,int l,int r){
//     if(l==r){
//         tb[x].v=max(tb[x].v,ta[x].v);
//         return ;
//     }

//     int mid=(l+r)>>1;
//     updateB(x<<1,l,mid);
//     updateB(x<<1|1,mid+1,r);
//     tb[x].mx=max(tb[x<<1].mx,tb[x<<1|1].mx);
// }


signed main() {
    // freopen("P6242_1.in", "r", stdin);
    // freopen("chfran.out", "w", stdout);
    // cerr<<1.00*(&f2-&f1)/1024/1024<<endl;
    n=rd;m=rd;
    for(int i=1;i<=n;i++)a[i]=rd;

    build(1,1,n);
    // int c=0;
    while(m--){
        // cerr<<"id="<<++c<<' ';
        int op=rd,l=rd,r=rd;
        if(op==1){
            int k=rd;
            changeAdd(1,1,n,l,r,k);
        }if(op==2){
            int v=rd;
            changeMin(1,1,n,l,r,v);
        }if(op==3){
            cout<<querySum(1,1,n,l,r)<<endl;

        }if(op==4){
            cout<<queryMaxA(1,1,n,l,r)<<endl;
        }if(op==5){
            cout<<queryMaxB(1,1,n,l,r)<<endl;

        }

    }
    return 0;
}

/*
1
2 5 1 
0 0 1 
0 0 4 

*/