首先可以有一个平方复杂度的 \(DP\)

设 \(f_{i,j}\) 表示前面 \(i\) 个小格，高度为 \(j\) 的最大答案

令 \(h_i\) 表示隔板 \(i\) 的高度

当 \(j\le h_i\) 时，转移到 \(f_{i+1,k},k\in [0,h_i]\)

否则 \(f{i,j}\rightarrow f_{i+1,j}\)

\(m\) 个限制直接区间加法就好了

只需要做到区间对一个数取 \(max\)，区间加法，区间询问 \(max\) 即可

直接令标记 \((a,b)\) 表示加 \(a\) 后对 \(b\) 取 \(max\)，用在线段树上就好了

# include 
    
     using namespace std;typedef long long ll;const int maxn(3e5 + 5);int n, m, test, o[maxn], len, h[maxn], ans, mx[maxn << 2];vector 
     
       v1[maxn], v0[maxn];struct Lazy_Tag {    int ad, mx;    inline Lazy_Tag operator +(Lazy_Tag b) const {        return (Lazy_Tag){ad + b.ad, max(mx + b.ad, b.mx)};    }    inline int Calc(int x) {        return max(x + ad, mx);    }} tag[maxn << 2];inline void Puttag(int x, Lazy_Tag v) {    tag[x] = tag[x] + v, mx[x] = v.Calc(mx[x]);}inline void Pushdown(int x) {    if (!tag[x].ad && !tag[x].mx) return;    Puttag(x << 1, tag[x]), Puttag(x << 1 | 1, tag[x]);    tag[x].ad = tag[x].mx = 0;}void Modify(int x, int l, int r, int ql, int qr, Lazy_Tag v) {    if (ql <= l && qr >= r) Puttag(x, v);    else {        int mid = (l + r) >> 1;        Pushdown(x);        if (ql <= mid) Modify(x << 1, l, mid, ql, qr, v);        if (qr > mid) Modify(x << 1 | 1, mid + 1, r, ql, qr, v);        mx[x] = max(mx[x << 1], mx[x << 1 | 1]);    }}int Query(int x, int l, int r, int ql, int qr) {    if (ql <= l && qr >= r) return mx[x];    else {        int mid = (l + r) >> 1, ret = 0;        Pushdown(x);        if (ql <= mid) ret = Query(x << 1, l, mid, ql, qr);        if (qr > mid) ret = max(ret, Query(x << 1 | 1, mid + 1, r, ql, qr));        mx[x] = max(mx[x << 1], mx[x << 1 | 1]);        return ret;    }}int main() {    int i, j, p, l1, l2, y, k;    scanf("%d", &test);    while (test--) {        memset(mx, 0, sizeof(mx)), memset(tag, 0, sizeof(tag));        scanf("%d%d", &n, &m), o[len = 1] = 1e9;        for (i = 1; i < n; ++i) scanf("%d", &h[i]), o[++len] = h[i];        for (i = 1; i <= n; ++i) v1[i].clear(), v0[i].clear();        for (i = 1; i <= m; ++i) {            scanf("%d%d%d", &p, &y, &k), ++y;            k ? v1[p].push_back(y) : v0[p].push_back(y);            o[++len] = y, o[++len] = y - 1;        }        sort(o + 1, o + len + 1), len = unique(o + 1, o + len + 1) - o - 1;        for (i = 1; i < n; ++i) h[i] = lower_bound(o + 1, o + len + 1, h[i]) - o;        for (i = 1; i <= n; ++i) sort(v1[i].begin(), v1[i].end()), sort(v0[i].begin(), v0[i].end());        for (i = 1; i <= n; ++i) {            l1 = v1[i].size(), l2 = v0[i].size();            for (j = 0; j < l1; ++j) {                y = lower_bound(o + 1, o + len + 1, v1[i][j]) - o;                Modify(1, 1, len, y, len, (Lazy_Tag){1, 0});            }            for (j = 0; j < l2; ++j) {                y = lower_bound(o + 1, o + len + 1, v0[i][j]) - o;                if (y > 1) Modify(1, 1, len, 1, y - 1, (Lazy_Tag){1, 0});            }            if (i == n) break;            y = Query(1, 1, len, 1, h[i]);            Modify(1, 1, len, 1, h[i], (Lazy_Tag){0, y});        }        printf("%d\n", mx[1]);    }    return 0;}