实际上问题就是每次覆盖一个区间 $[l,r] = x$，以及从 $l$ 出发向右覆盖一个等差数列，$r$ 出发向右覆盖一个等差数列。

对于这里的覆盖，指的是求最大值，然后每次查询一个区间的最大值。

分别考虑，对于区间覆盖求最值是很容易的基础线段树操作，关键是等差数列如何维护。

线段树暴力维护等差数列是可以的，在 $tag$ 维护时带入一个结构体，记录 $tag[i].p$ 和 $tag[i].x$ 分别表示当前这个区间的 $tag$ 是从哪个点过来的以及一开始的值是几，那么就可以维护了。

但是这样做比较麻烦，可以从另一个角度考虑：

对于任何一次查询，询问区间为 $[Q_l, Q_r]$。由于音量向两侧递减，广场舞音箱对这个查询区间的影响只可能来自三个方向：

• 音箱正好在查询区间内部或有重叠（对应代码中的 ans1）：
  • 如果阿姨们占领的区域与查询区间 $[Q_l, Q_r]$ 有交集，那么在交集区域内，音量是没有衰减的（也就是音量最高点 $x$）。
  • 直接用一棵最普通的基础线段树 maxv，维护区间的最大值。插入时进行区间更新，查询时直接查询该区间的最值即可。
• 音箱在查询区间的左侧（对应代码中的 ans2）：
  • 如果声源 $i$ 在查询区间的左侧（即 $i \le Q_l$），声音会向右传播并不断衰减。由于声音越往右越弱，那么这段声音对 $[Q_l, Q_r]$ 区间造成的最大音量，必然出现在查询区间的最左端点 $Q_l$ 处。
  • 假设声源在 $i$ 点，原始音量为 $v$。传到 $Q_l$ 点的距离是 $Q_l - i$。 此时在 $Q_l$ 听到的音量为：$v - (Q_l - i)$。将其拆解重组为 $(v + i) - Q_l$。 因为在一次查询中，$Q_l$ 是固定的常量，我们只需要让 $(v + i)$ 尽可能大即可。
  • 建立第二棵线段树 maxl，每次发生事件时，在声源位置 $i$ 单点记录其 $v + i$ 的值。查询时，只需在 $[1, Q_l]$ 范围内查出最大的 $v + i$，最后减去常量 $Q_l$ 即可。
• 音箱在查询区间的右侧（对应代码中的 ans3）：
  • 同理，如果声源 $i$ 在查询区间的右侧（即 $i \ge Q_r$），声音向左传播衰减。它对 $[Q_l, Q_r]$ 造成的最大影响，必然出现在查询区间的最右端点 $Q_r$ 处。
  • 传到 $Q_r$ 点的距离是 $i - Q_r$。在 $Q_r$ 听到的音量为：$v - (i - Q_r)$。 重组为 $(v - i) + Q_r$。
  • 建立第三棵线段树 maxr，每次单点记录 $v - i$ 的值。查询时，在 $[Q_r, n]$ 范围内查出最大的 $v - i$，最后加上常量 $Q_r$ 即可。

最终，针对每次查询，只需要求 $\max(ans1, ans2, ans3)$ 就能涵盖所有方向的声源影响，得到绝对正确的最大值。

假设街道只有 10 个区域，发生了一起事件：阿姨们在 $[2, 3]$ 区域跳舞，音量为 $10$。 代码在处理更新时：

• 在 maxv 中区间 $[2, 3]$ 更新最大值为 $10$。
• 在 maxl 中更新声源点。左端点 $i=2$ 存入 $v+i = 12$；右端点 $i=3$ 存入 $v+i = 13$。
• 在 maxr 中更新声源点。左端点 $i=2$ 存入 $v-i = 8$；右端点 $i=3$ 存入 $v-i = 7$。

查询场景 A：查询区间为 $[5, 7]$（询问右侧区域）：此时声源 $[2, 3]$ 完全在查询区间的左侧。

• ans1 (区间内部)：$[5, 7]$ 内没有音箱覆盖，返回 $0$。
• ans2 (左侧声源影响)：查询 $[1, 5]$ 范围内 maxl 的最大值，显然是声源点 $3$ 存的 $13$。 计算得出：$ans2 = 13 - Q_l = 13 - 5 = 8$。（符合实际规律：在 $3$ 号位音量为 $10$，隔了 $2$ 个身位传到 $5$ 号位，音量衰减为 $8$）。
• ans3 (右侧声源影响)：查询 $[7, 10]$ 内 maxr，没有声源，负无穷。
• 结果：最大值为 $ans2 = 8$。

查询场景 B：查询区间为 $[1, 1]$（询问左侧区域）：此时声源 $[2, 3]$ 完全在查询区间的右侧。

• ans1 (区间内部)：$[1, 1]$ 无覆盖，返回 $0$。
• ans2 (左侧影响)：查询 $[1, 1]$，无声源，负无穷。
• ans3 (右侧影响)：查询 $[1, 10]$ 内 maxr 的最大值，显然是声源点 $2$ 存的 $8$。 计算得出：$ans3 = 8 + Q_r = 8 + 1 = 9$。（符合实际规律：从 $2$ 号位传到 $1$ 号位距离为 $1$，音量衰减为 $9$）。
• 结果：最大值为 $ans3 = 9$。

为什么只更新区间端点 $l$ 和 $r$ 的单点？

因为当声源 $[l, r]$ 向右传播时，离右边最近的点 $r$ 必定提供最大的 $v+i$（即 $10+3=13 > 10+2=12$）；同理向左传播时，离左边最近的 $l$ 提供最大的 $v-i$。区间的内部点永远无法在向外辐射时成为最强者，所以根本不需要耗费时间去更新内部的点。

标程

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 500005
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

int n, t;
LL maxv[N << 2], maxl[N << 2], maxr[N << 2], tag[N << 2];

void up(int p) {
    maxv[p] = max(tag[p], max(maxv[lc], maxv[rc]));
    maxl[p] = max(maxl[lc], maxl[rc]);
    maxr[p] = max(maxr[lc], maxr[rc]);
}

void update_range(int ql, int qr, LL v, int l, int r, int p) {
    if (ql <= l && r <= qr) {
        maxv[p] = max(maxv[p], v);
        tag[p] = max(tag[p], v);
        return;
    }
    if (ql <= mid) update_range(ql, qr, v, l, mid, lc);
    if (qr > mid) update_range(ql, qr, v, mid + 1, r, rc);
    up(p);
}

LL query_range(int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) return maxv[p];
    LL res = tag[p];
    if (ql <= mid) res = max(res, query_range(ql, qr, l, mid, lc));
    if (qr > mid) res = max(res, query_range(ql, qr, mid + 1, r, rc));
    return res;
}

void update_l(int x, LL v, int l, int r, int p) {
    if (l == r) {
        maxl[p] = max(maxl[p], v + l);
        return;
    }
    if (x <= mid) update_l(x, v, l, mid, lc);
    if (x > mid) update_l(x, v, mid + 1, r, rc);
    up(p);
}

LL query_l(int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) return maxl[p];
    LL res = -INF;
    if (ql <= mid) res = max(res, query_l(ql, qr, l, mid, lc));
    if (qr > mid) res = max(res, query_l(ql, qr, mid + 1, r, rc));
    return res;
}

void update_r(int x, LL v, int l, int r, int p) {
    if (l == r) {
        maxr[p] = max(maxr[p], v - l);
        return;
    }
    if (x <= mid) update_r(x, v, l, mid, lc);
    if (x > mid) update_r(x, v, mid + 1, r, rc);
    up(p);
}

LL query_r(int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) return maxr[p];
    LL res = -INF;
    if (ql <= mid) res = max(res, query_r(ql, qr, l, mid, lc));
    if (qr > mid) res = max(res, query_r(ql, qr, mid + 1, r, rc));
    return res;
}

int main() {
    scanf("%d %d", &n, &t);
    for (int i = 0; i <= 4 * n; i++) {
        tag[i] = maxv[i] = 0;
        maxl[i] = maxr[i] = -INF;
    }
    while (t--) {
        int op, l, r, x;
        scanf("%d %d %d", &op, &l, &r);
        if (op == 1) {
            scanf("%d", &x);
            update_range(l, r, x, 1, n, 1);
            update_l(l, x, 1, n, 1);
            update_l(r, x, 1, n, 1);
            update_r(l, x, 1, n, 1);
            update_r(r, x, 1, n, 1);
        } else {
            LL ans1 = query_range(l, r, 1, n, 1);
            LL ans2 = query_l(1, l, 1, n, 1) - l;
            LL ans3 = query_r(r, n, 1, n, 1) + r;
            printf("%lld\n", max(ans1, max(ans2, ans3)));
        }
    }
    return 0;
}

方法二

根据题意，阿姨们占领连续区域 $[l, r]$ 并在每个区域放置音量为 $p$ 的音箱。由于同一群阿姨带来的音箱会进行蓝牙连接且音量随距离每增加 $1$ 个区域衰减 $1$，对于任意一次事件 $(l, r, p)$，街道上每个区域 $x$ 实际受到的音量影响可以划分为三段一次函数（线段）：

• 覆盖区 ( $l \le x \le r$ )：音量保持不变，解析式为 $y = 0 \cdot x + p$。
• 左侧衰减区 ( $l-p+1 \le x \le l-1$ )：距离左边界的距离为 $l-x$，音量为 $p - (l-x)$，整理得解析式为 $y = x + (p - l)$。
• 右侧衰减区 ( $r+1 \le x \le r+p-1$ )：距离右边界的距离为 $x-r$，音量为 $p - (x-r)$，整理得解析式为 $y = -x + (p + r)$。

当多个群体的阿姨先后到来时，任意区域 $x$ 历史听到的最大音量即为所有历史线段在该点函数值的最大值（即求多条线段的上包络线）。对于每次查询，我们需要快速求出区间 $[i, j]$ 历史最大音量的最大值。这可以通过李超线段树来实现。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 500005
#define LL long long
#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

int n, t;
LL k[N << 2], b[N << 2], max_y[N << 2];

// 向上更新区间内的历史最大值
void up(int l, int r, int p) {
    max_y[p] = max(k[p] * l + b[p], k[p] * r + b[p]);
    if (l < r) {
        max_y[p] = max({max_y[p], max_y[lc], max_y[rc]});
    }
}

// 李超树单节点插入线段
void insert_line(LL K, LL B, int l, int r, int p) {
    if (l == r) {
        if (K * l + B > k[p] * l + b[p]) {
            k[p] = K;
            b[p] = B;
        }
        up(l, r, p);
        return;
    }
    // 判断中点哪条线段更优
    if (K * mid + B > k[p] * mid + b[p]) {
        swap(K, k[p]);
        swap(B, b[p]);
    }
    // 将劣势线段下传至能反超的一侧
    if (K * l + B > k[p] * l + b[p]) {
        insert_line(K, B, l, mid, lc);
    } else if (K * r + B > k[p] * r + b[p]) {
        insert_line(K, B, mid + 1, r, rc);
    }
    up(l, r, p);
}

// 线段树区间更新
void update(int ql, int qr, LL K, LL B, int l, int r, int p) {
    if (ql <= l && r <= qr) {
        insert_line(K, B, l, r, p);
        return;
    }
    if (ql <= mid) update(ql, qr, K, B, l, mid, lc);
    if (qr > mid) update(ql, qr, K, B, mid + 1, r, rc);
    up(l, r, p);
}

// 线段树区间查询
LL query(int ql, int qr, int l, int r, int p) {
    LL L = max(l, ql), R = min(r, qr);
    // 先计算当前节点存储的线段在交集区间的作用
    LL res = max(k[p] * L + b[p], k[p] * R + b[p]);
    // 恰好完全包含，直接合并整棵子树的历史最值
    if (ql <= l && r <= qr) return max(res, max_y[p]);
    if (ql <= mid) res = max(res, query(ql, qr, l, mid, lc));
    if (qr > mid) res = max(res, query(ql, qr, mid + 1, r, rc));
    return res;
}

int main() {
    scanf("%d %d", &n, &t);
    while (t--) {
        int op, l, r, x;
        scanf("%d %d %d", &op, &l, &r);
        if (op == 1) {
            scanf("%d", &x);
            // 核心覆盖区：y = p
            update(l, r, 0, x, 1, n, 1);
            // 左侧衰减区：y = x + (p - l)
            int lst = max(1, l - x + 1);
            int led = l - 1;
            // 右侧衰减区：y = -x + (p + r)
            int rst = r + 1;
            int red = min(n, r + x - 1);
            if (lst <= led) update(lst, led, 1, x - l, 1, n, 1);
            if (rst <= red) update(rst, red, -1, x + r, 1, n, 1);
        } else if (op == 2) {
            printf("%lld\n", query(l, r, 1, n, 1));
        }
    }
    return 0;
}

原题面等价于每次选择区间执行区间常数 chkmax ，区间等差数列 chkmax ，直接硬维护就行。