题解：体育课高兴值问题

算法思路

本题需要维护一个序列，支持三种操作：区间查询最大值、交换元素、区间等差数列加法。采用分块+凸包的方法高效处理。

1. 问题分析

• 高兴值计算：对于位置 $i$，高兴值为 $\max(0, a_i - a_1)$
• 操作类型：
  1. 查询区间最大高兴值
  2. 交换两个位置的元素
  3. 区间等差数列加法：第 $l$ 个加 $t$，第 $l+1$ 个加 $2t$，...，第 $r$ 个加 $(r-l+1)t$

2. 关键难点

第三种操作是等差数列加法，传统的线段树难以直接处理。采用分块维护，每个块内使用凸包来维护最大值。

3. 分块设计

• 将序列分成 $\sqrt{n}$ 个块
• 每个块维护：
  • 懒标记 $k$ 和 $b$，表示整体加 $k \cdot x + b$
  • 凸包结构，用于快速查询块内最大值

4. 凸包维护

对于每个块，维护一个上凸壳：

• 点集：$(i, a_i)$
• 斜率单调递减
• 查询时在凸壳上二分查找最大值

代码实现

#include <bits/stdc++.h>
#define int long long
#define N 100000
#define M 1000
#define Inf (1ll * INT_MAX * N)
#define Ins (1ll * INT_MIN * N)
using namespace std;

double const eps = 1e-12;
int n, m, a[N + 5], b[N + 5], block, opt, ux, uy, uz;

struct Blcok {
    struct Node {
        int x, y;
    };
    
    int top, tip, b, k, l, r;
    Node sta[M + 5];
    
    // 计算两点连线斜率
    double calc(Node x, Node y) {
        return (x.y - y.y) * 1.0 / (x.x - y.x);
    }
    
    // 向凸包中添加点
    void modify(Node x) {
        while (top > 1 && calc(x, sta[top]) - calc(sta[top], sta[top - 1]) >= eps)
            top--;
        tip = min(top, tip), sta[++top] = x;
    }
    
    // 查询当前斜率下的最大值点
    Node query() {
        while (tip < top && calc(sta[tip], sta[tip + 1]) + k >= eps)
            tip++;
        return sta[tip];
    }
    
    // 初始化块：应用懒标记，重建凸包
    void init() {
        for (int i = l; i <= r; i++)
            a[i] += i * k + b;
        b = k = 0, top = tip = 1, sta[1] = {l - 1, 0};
    }
    
    // 构建凸包
    void build() {
        for (int i = l; i <= r; i++)
            modify({i, a[i]});
    }
    
    // 获取块内最大值
    int getMax() {
        Node res = query();
        return res.y + res.x * k + b;
    }
} q[M + 5];

// 读取输入
int read() {
    int f = 1, g = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        g = g * 10 + ch - '0';
        ch = getchar();
    }
    return f * g;
}

// 查询区间最大值
int getMax(int l, int r) {
    int bl = b[l], br = b[r], ans = Ins;
    
    // 处理不完整的块
    if (q[bl].l != l) bl++;
    if (q[br].r != r) br--;
    
    // 整个查询在同一个块内
    if (bl > br && b[l] == b[r]) {
        for (int i = l; i <= r; i++)
            ans = max(ans, a[i] + i * q[b[i]].k + q[b[i]].b);
        return ans;
    }
    
    // 处理左右不完整的块
    for (int i = l; b[i] != bl; i++)
        ans = max(ans, a[i] + i * q[b[i]].k + q[b[i]].b);
    for (int i = r; b[i] != br; i--)
        ans = max(ans, a[i] + i * q[b[i]].k + q[b[i]].b);
    
    // 处理完整的块
    for (int i = bl; i <= br; i++)
        ans = max(ans, q[i].getMax());
    
    return ans;
}

// 区间等差数列加法
void upd(int l, int r, int v) {
    int bl = b[l], br = b[r];
    
    if (q[bl].l != l) bl++;
    if (q[br].r != r) br--;
    
    // 整个操作在同一个块内
    if (bl > br && b[l] == b[r]) {
        q[b[l]].init();
        for (int i = l; i <= r; i++)
            a[i] += v * (i - l + 1);
        q[b[l]].build();
        return;
    }
    
    // 处理左右不完整的块
    q[b[l]].init();
    for (int i = l; b[i] != bl; i++)
        a[i] += v * (i - l + 1);
    q[b[l]].build();
    
    q[b[r]].init();
    for (int i = r; b[i] != br; i--)
        a[i] += v * (i - l + 1);
    q[b[r]].build();
    
    // 处理完整的块：更新懒标记
    for (int i = bl; i <= br; i++)
        q[i].k += v, q[i].b += (1 - l) * v;
}

// 交换两个元素
void Swap(int l, int r) {
    int bl = b[l], br = b[r];
    
    if (bl == br) {
        q[bl].init();
        swap(a[l], a[r]);
        q[bl].build();
        return;
    }
    
    q[bl].init(), q[br].init();
    swap(a[l], a[r]);
    q[bl].build(), q[br].build();
}

main() {
    n = read(), m = read(), block = ceil(sqrt(n));
    
    // 初始化序列和分块
    for (int i = 1; i <= n; i++)
        a[i] = read(), b[i] = (i - 1) / block + 1;
    
    // 初始化每个块
    for (int i = 1; i <= (n - 1) / block + 1; i++) {
        q[i].k = q[i].b = 0;
        q[i].l = (i - 1) * block + 1;
        q[i].r = min(n, i * block);
        q[i].init();
        q[i].build();
    }
    
    // 处理操作
    for (int i = 1; i <= m; i++) {
        opt = read();
        
        if (opt == 1) {
            ux = read(), uy = read();
            int max_val = getMax(ux, uy);
            int first_val = a[1] + q[b[1]].k * 1 + q[b[1]].b;
            cout << max(0ll, max_val - first_val) << endl;
        } else if (opt == 2) {
            ux = read(), uy = read();
            Swap(ux, uy);
        } else if (opt == 3) {
            ux = read(), uy = read(), uz = read();
            upd(ux, uy, uz);
        }
    }
    
    return 0;
}

关键优化

1. 凸包维护：每个块维护上凸壳，支持 $O(1)$ 查询最大值
2. 懒标记：对于等差数列加法，使用 $k$ 和 $b$ 标记，避免频繁重建凸包
3. 分块策略：平衡查询和修改的复杂度
4. 边界处理：精细处理跨块操作

复杂度分析

• 查询操作：$O(\sqrt{n})$
• 修改操作：$O(\sqrt{n})$
• 交换操作：$O(\sqrt{n})$
• 空间复杂度：$O(n)$

该算法能够高效处理 $10^5$ 规模的数据，满足题目要求。