CF1887C Minimum Array
小丑做法。
首先差分一下，转化成两次单点加。每次考虑前 \(i\) 位，然后一直维护当前合法的时刻区间，这个东西怎么做呢？可以离线下来记录每个点被那些操作波及，然后算一遍前缀和，对于合法的区间区间打标记。需要支持区间加 \(1\) 和查询最大值，用线段树维护。复杂度 \(O(n + q \log n)\)。
const int N = 1e6 + 10;
int n;
int m, L[N], R[N];
LL val[N], d[N], a[N];
vector<pii> vec[N];
struct SegmentTree {
int tr[N << 2], tag[N << 2];
#define lc (k << 1)
#define rc (k << 1 | 1)
#define mid (l + r) / 2
void update(int k) {
tr[k] = max(tr[lc], tr[rc]);
}
void addtag(int k, int x) {
tr[k] += x, tag[k] += x;
}
void pushdown(int k) {
if(tag[k]) {
addtag(lc, tag[k]);
addtag(rc, tag[k]);
tag[k] = 0;
}
}
void modify(int k, int l, int r, int L, int R) {
if(r < L || R < l) return ;
if(L <= l && r <= R) {
addtag(k, 1);
return ;
}
pushdown(k);
modify(lc, l, mid, L, R);
modify(rc, mid + 1, r, L, R);
update(k);
}
int query(int k, int l, int r, int L, int R) {
if(r < L || R < l) return 0;
if(L <= l && r <= R) return tr[k];
pushdown(k);
return max(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
}
void build(int k, int l, int r) {
tr[k] = tag[k] = 0;
if(l == r) return ;
build(lc, l, mid), build(rc, mid + 1, r);
}
}seg;
int query(int l, int r) {
return seg.query(1, 1, m + 1, l + 1, r + 1);
}
void modify(int l, int r) {
seg.modify(1, 1, m + 1, l + 1, r + 1);
}
void clear() {
for(int i = 1; i <= n; ++i)
d[i] = 0, vec[i].clear();
}
void solve() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]);
read(m);
clear();
seg.build(1, 1, m + 1);
for(int i = 1; i <= n; ++i)
vec[i].emplace_back(mp(0, 0));
for(int i = 1; i <= m; ++i) {
read(L[i], R[i], val[i]);
vec[L[i]].emplace_back(mp(i, val[i]));
vec[R[i] + 1].emplace_back(mp(i, -val[i]));
}
for(int i = 1; i <= n; ++i) {
LL s = 0, mn = 1e18;
vec[i].emplace_back(mp(m + 1, 0));
for(int j = 0; j < sz(vec[i]) - 1; ++j) {
s += vec[i][j].second;
if(vec[i][j].first < vec[i][j + 1].first && s < mn && query(vec[i][j].first, vec[i][j + 1].first - 1) == i - 1)
mn = min(mn, s);
}
s = 0;
for(int j = 0; j < sz(vec[i]) - 1; ++j) {
s += vec[i][j].second;
if(vec[i][j].first < vec[i][j + 1].first && s == mn && query(vec[i][j].first, vec[i][j + 1].first - 1) == i - 1)
modify(vec[i][j].first, vec[i][j + 1].first - 1);
}
d[i] = mn;
}
for(int i = 1; i <= n; ++i)
d[i] += d[i - 1], printf("%lld ",a[i] + d[i]);
puts("");
}
int main() {
int T; read(T);
while(T--) solve();
}