首先可以有一个平方复杂度的 \(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 <bits/stdc++.h>
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 <int> 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;
}