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();  
}