区间最大字段和问题（线段树）

吉司机线段树

0.吉司机的前言

1.介绍

吉司机线段树主要用于2件事，一个是区间最值修改，一个是区间历史最值维护。

2.区间最值

给定一个长度为n的数列A，接着有m次操作

1. 区间[l,r]中所有数变为$min(A_i,x)$
2. 询问区间[l,r]和
   使用$O(n\log n)数据结构$

用线段树解题一般我们使用lazytag来实现高效的时间复杂度。但是本题怎么设计？如果用一个tag处理区间最值，另一个处理区间和，但是这个和修改区间最值没有任何直接关系，不能这么简单处理。

吉司机线段树将这一类区间最值进行了通用转化方法，时间复杂度达到了$O(n\log n)$。首先维护如下标记

• 区间最大值mx
• 区间最大值出现次数mxcnt
• 区间次大值se
• 区间和sum

考虑区间最值修改操作，即用$min(A_i,x)$替换区间$[L,R]$的每个节点$a_i$，首先找到对应区间，让后暴力搜索，我们搜到某个节点时，会分成以下三种情况。

1. 当$x\ge mx$，显然这次修改不影响该节点，return
2. 当$se<x\le mx$，这次操作影响她的最大值，那么$sum=sum-(mx-x)\times mxcnt$
3. 当$x\le se$，这个时候就不能直接修改了，只能递归左右儿子，让后在pushup中解决

上述算法的关键就是次大值，起到了剪枝的关键作用。

这个的时间复杂度是$O(n\log n)$ 。

3.历史最值

直接上板子题罢

线段树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$ 的最大值。

对于前四种操作，我们完全可以和上面那个题写起来一模一样，而操作瓶颈在于5。

我们观察一下tag的变化，tag的变化可能变大也可能变小，但在下传的时候当前节点儿子的值是不会改变的。

那么也就是说：只有当tag达到最大的时候，下传才能让儿子达到最大

那么也就是说，我们可以记录一个最大的懒标记。

如何下传？我们应当先更新$maxb$再更新$maxa$，先更新最大懒标记在更新懒标记。

让后就没有让后了…

#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define ll long long
using namespace std;
constexpr int MN = 5e6 + 15, NINF = -2e9;
template <typename type>
inline void read(type &x)
{
    x = 0;
    bool flag(0);
    char ch = getchar();
    while (!isdigit(ch))
        flag = ch == '-', ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    flag ? x = -x : 0;
}
int n, m;
struct segtree
{
    ll sum;
    int l, r, maxa, maxb, se, mxcnt;
    int add1, add2, mxadd1, mxadd2;
} t[MN << 2];

void pushup(int p)
{
    t[p].sum = t[ls].sum + t[rs].sum;
    t[p].maxa = max(t[ls].maxa, t[rs].maxa);
    t[p].maxb = max(t[ls].maxb, t[rs].maxb);

    if (t[ls].maxa == t[rs].maxa)
    {
        t[p].se = max(t[ls].se, t[rs].se);
        t[p].mxcnt = t[ls].mxcnt + t[rs].mxcnt;
    }
    else if (t[ls].maxa > t[rs].maxa)
    {
        t[p].se = max(t[ls].se, t[rs].maxa);
        t[p].mxcnt = t[ls].mxcnt;
    }
    else
    {
        t[p].se = max(t[ls].maxa, t[rs].se);
        t[p].mxcnt = t[rs].mxcnt;
    }
}

void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        read(t[p].maxa);
        t[p].sum = t[p].maxb = t[p].maxa;
        t[p].se = NINF;
        t[p].mxcnt = 1;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

void doit(int k1, int k2, int k3, int k4, int p)
{
    // 更新历史最大值
    t[p].maxb = max(t[p].maxb, t[p].maxa + k3);
    // 更新当前最大值
    t[p].maxa += k1;
    // 更新区间和
    t[p].sum += 1ll * k1 * t[p].mxcnt + 1ll * k2 * (t[p].r - t[p].l + 1 - t[p].mxcnt);
    // 更新次大值
    if (t[p].se != NINF)
        t[p].se += k2;
    // 更新标记
    t[p].mxadd1 = max(t[p].mxadd1, t[p].add1 + k3);
    t[p].mxadd2 = max(t[p].mxadd2, t[p].add2 + k4);
    t[p].add1 += k1;
    t[p].add2 += k2;
}

void pushdown(int p)
{
    int maxn = max(t[ls].maxa, t[rs].maxa);
    if (t[ls].maxa == maxn)
    {
        doit(t[p].add1, t[p].add2, t[p].mxadd1, t[p].mxadd2, ls);
    }
    else
    {
        doit(t[p].add2, t[p].add2, t[p].mxadd2, t[p].mxadd2, ls);
    }
    if (t[rs].maxa == maxn)
    {
        doit(t[p].add1, t[p].add2, t[p].mxadd1, t[p].mxadd2, rs);
    }
    else
    {
        doit(t[p].add2, t[p].add2, t[p].mxadd2, t[p].mxadd2, rs);
    }
    t[p].add1 = t[p].add2 = t[p].mxadd1 = t[p].mxadd2 = 0;
}

void updateadd(int p, int fl, int fr, ll k)
{
    if (t[p].l >= fl && t[p].r <= fr)
    {
        t[p].sum += 1ll * k * (t[p].r - t[p].l + 1);
        t[p].maxa += k;
        t[p].maxb = max(t[p].maxb, t[p].maxa);
        if (t[p].se != NINF)
            t[p].se += k;
        t[p].add1 += k;
        t[p].add2 += k;
        t[p].mxadd1 = max(t[p].mxadd1, t[p].add1);
        t[p].mxadd2 = max(t[p].mxadd2, t[p].add2);
        return;
    }
    pushdown(p);
    int mid = t[p].l + t[p].r >> 1;
    if (mid >= fl)
        updateadd(ls, fl, fr, k);
    if (mid < fr)
        updateadd(rs, fl, fr, k);
    pushup(p);
}

void updatemin(int p, int fl, int fr, int v)
{
    if (v >= t[p].maxa || t[p].l > fr || t[p].r < fl)
        return;
    if (t[p].l >= fl && t[p].r <= fr && v > t[p].se)
    {
        int k = t[p].maxa - v;
        t[p].sum -= 1ll * k * t[p].mxcnt;
        t[p].maxa = v;
        t[p].maxb = max(t[p].maxb, v); // 更新历史最大值
        t[p].add1 -= k;
        return;
    }
    pushdown(p);
    updatemin(ls, fl, fr, v);
    updatemin(rs, fl, fr, v);
    pushup(p);
}

ll querysum(int p, int fl, int fr)
{
    if (t[p].l >= fl && t[p].r <= fr)
    {
        return t[p].sum;
    }
    pushdown(p);
    int mid = t[p].l + t[p].r >> 1;
    ll res = 0;
    if (mid >= fl)
        res += querysum(ls, fl, fr);
    if (mid < fr)
        res += querysum(rs, fl, fr);
    return res;
}

int querymaxa(int p, int fl, int fr)
{
    if (t[p].l >= fl && t[p].r <= fr)
    {
        return t[p].maxa;
    }
    pushdown(p);
    int res = NINF;
    int mid = t[p].l + t[p].r >> 1;
    if (mid >= fl)
        res = querymaxa(ls, fl, fr);
    if (mid < fr)
        res = max(res, querymaxa(rs, fl, fr));
    return res;
}

int querymaxb(int p, int fl, int fr)
{
    if (t[p].l >= fl && t[p].r <= fr)
    {
        return t[p].maxb;
    }
    pushdown(p);
    int res = NINF;
    int mid = t[p].l + t[p].r >> 1;
    if (mid >= fl)
        res = querymaxb(ls, fl, fr);
    if (mid < fr)
        res = max(res, querymaxb(rs, fl, fr));
    return res;
}

int main()
{
    read(n);
    read(m);
    build(1, 1, n);
    int op, x, y, z;
    while (m--)
    {
        read(op);
        read(x);
        read(y);
        if (op == 1)
        {
            read(z);
            updateadd(1, x, y, z);
        }
        else if (op == 2)
        {
            read(z);
            updatemin(1, x, y, z);
        }
        else if (op == 3)
        {
            cout << querysum(1, x, y) << '\n';
        }
        else if (op == 4)
        {
            cout << querymaxa(1, x, y) << '\n';
        }
        else if (op == 5)
        {
            cout << querymaxb(1, x, y) << '\n';
        }
    }
    return 0;
}