题解

每张卡选或不选，共有 $2^m$ 种方案。难点在于，卡之间会重叠，使用一张卡以后，最大值和最小值的位置还可能改变。

可以先把这两个位置固定下来。设我们想让位置 $i$ 的读数减去位置 $k$ 的读数尽量大，看看一张降温量为 $d$ 的卡对这个差的影响。

覆盖情况	对读数差的影响	是否使用
只覆盖 $k$	增加 $d$	使用
只覆盖 $i$	减少 $d$	不使用
同时覆盖两者	不变	都可以
两者都不覆盖

因此，对固定的一对 $(i,k)$，选择已经确定了。用掉所有覆盖 $k$ 且不覆盖 $i$ 的卡，就能让这对位置的差最大。

只枚举较大值的位置

如果只固定 $i$，把所有不覆盖 $i$ 的卡都用掉，会发生什么？

对任意一个 $k$，这些卡里覆盖 $k$ 的部分恰好都是有利的卡，其他卡又不会改变 $i,k$ 的差。所以这一次用卡，实际上同时做到了每个 $k$ 对应的最优选择。

记使用这些卡后的数组为 $b^{(i)}$。位置 $i$ 完全没被修改，仍是 $a_i$，于是固定 $i$ 时只需计算

$$a_i-\min_k b^{(i)}_k.$$

再枚举 $i$ 取最大值。

这里没有强行要求 $i$ 一定是操作后的最大值位置。上式算的是一个合法方案中某两个位置的差，因此不会超过真正的最优温差。另一方面，取最优方案里真正的最大、最小值位置为 $i,k$，我们已经证明，按上面规则选卡，能让这两个位置的差至少和原来一样大。因此答案也不会漏掉。

做到这里，每次枚举 $i$ 都重做一遍差分，已经能得到 $O(n(n+m))$ 的做法。

相邻两个 $i$ 之间，只会有少量卡改变状态

我们需要维护的数组有一个明确含义，当前只使用那些不包含 $i$ 的卡。

让 $i$ 从左向右移动。一张区间为 $[l,r]$ 的卡，会依次经历这三个阶段。

$$i<l\text{ 时使用}\quad\longrightarrow\quad l\le i\le r\text{ 时不用}\quad\longrightarrow\quad i>r\text{ 时使用}.$$

从 $i$ 走到 $i+1$，只需处理两种变化。

• 若某张卡的 $l=i+1$，新位置进入它的区间。原先用了它，现在要撤销，给 $[l,r]$ 加回 $d$。
• 若某张卡的 $r=i$，新位置离开它的区间。原先没用它，现在要使用，给 $[l,r]$ 减去 $d$。

其他卡是否包含当前位置都没变，不用处理。按左右端点分别存卡片编号，就能直接找到这些变化。

线段树维护数组 $b$，需要的操作只有区间加和全局最小值。节点存区间最小值，懒标记存整段加了多少；查询直接读根节点。

初始化 $i=1$，使用所有 $l>1$ 的卡。计算一次 $a_1-\min b$，然后按上面两种事件移动到下一个位置，再计算下一次候选值。不要把撤销和使用的正负号写反，也不要在事件处理到一半时查询。

每张卡最多经历常数次区间修改，每次 $O(\log n)$。总时间 $O(n+m\log n)$，也可以写成 $O((n+m)\log n)$；空间 $O(n+m)$。所有卡的降温量可能累加到 $2\times10^{14}$，读数、标记和答案都用 long long。$n=1$ 时同样按这个过程算，答案自然为 $0$。

性质分里的两种简化

每张卡只影响一个位置时，设位置 $k$ 用完全部卡后的值为 $v_k$。取位置 $i$ 做较大值，它保持 $a_i$，其他位置都可以降到最低，因此只需求

$$\max\left(0,\max_{i\ne k}(a_i-v_k)\right).$$

维护 $v$ 的最小值和次小值，以及它们各自的下标。枚举 $i$ 时排除自己，就能在线性时间里完成。相同数值、不同下标仍应算两个候选。这对应单点卡的 15 分，时间 $O(n+m)$、空间 $O(n)$。

若所有区间互不相交，可以把每张卡控制的区间看成一个块，未覆盖的位置各自成块，降温量为 $0$。块 $t$ 的初始最大、最小值记为 $H_t,L_t$，降温量记为 $D_t$。

两个位置在同一块时，会一起下降，差最多为 $H_t-L_t$。在不同块 $s,t$ 时，可以让前一块不下降、后一块下降，差最多为 $H_s-(L_t-D_t)$。因此仍然维护最小值、次小值，只是这次排除的是同一个块，同时别忘了同块答案 $H_t-L_t$。各区间总长不超过 $n$，直接遍历划块，时间和空间均为 $O(n+m)$，对应 17 分。

这两档分别去掉了区间内部的关联、不同卡之间的重叠，允许不用线段树求解。

小规模还有两档。$n,m\le16$ 时枚举卡的子集，逐点执行后求温差，时间 $O(2^m(n+nm))$、额外空间 $O(n)$，对应 10 分。$n,m\le2000$ 时用前面固定 $i$ 后重做差分的办法，时间 $O(n(n+m))$、空间 $O(n+m)$，能拿前两档共 28 分。把规模做法与两种性质做法组合，可以保证前四档的 60 分。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct SegmentTree {
    int n;
    vector<ll> mn, lazy;
    SegmentTree(const vector<ll> &a) : n((int)a.size() - 1), mn(4 * n + 4), lazy(4 * n + 4) { build(1, 1, n, a); }
    void build(int p, int l, int r, const vector<ll> &a) {
        if (l == r) { mn[p] = a[l]; return; }
        int mid = (l + r) / 2;
        build(p * 2, l, mid, a);
        build(p * 2 + 1, mid + 1, r, a);
        mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
    }
    void apply(int p, ll x) { mn[p] += x; lazy[p] += x; }
    void push(int p) {
        if (!lazy[p]) return;
        apply(p * 2, lazy[p]);
        apply(p * 2 + 1, lazy[p]);
        lazy[p] = 0;
    }
    void add(int p, int l, int r, int ql, int qr, ll x) {
        if (ql <= l && r <= qr) { apply(p, x); return; }
        push(p);
        int mid = (l + r) / 2;
        if (ql <= mid) add(p * 2, l, mid, ql, qr, x);
        if (qr > mid) add(p * 2 + 1, mid + 1, r, ql, qr, x);
        mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
    }
    void add(int l, int r, ll x) { add(1, 1, n, l, r, x); }
    ll minimum() const { return mn[1]; }
};

struct Card { int l, r; ll d; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<Card> card(m);
    vector<vector<int>> byL(n + 2), byR(n + 2);
    for (int j = 0; j < m; ++j) {
        cin >> card[j].l >> card[j].r >> card[j].d;
        byL[card[j].l].push_back(j);
        byR[card[j].r].push_back(j);
    }
    SegmentTree seg(a);
    for (const auto &c : card) if (c.l > 1) seg.add(c.l, c.r, -c.d);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, a[i] - seg.minimum());
        if (i == n) break;
        for (int j : byL[i + 1]) seg.add(card[j].l, card[j].r, card[j].d);
        for (int j : byR[i]) seg.add(card[j].l, card[j].r, -card[j].d);
    }
    cout << ans << '\n';
}