题目可以看成一个最大流模型。源点 \(S\) 往所有机器人连边，容量为 \(c_i\)；所有容器往汇点 \(T\) 连边，容量为 \(a_i\)；机器人 \(i\) 往容器 \(j\in[l_i,r_i]\) 连边，容量 \(+\infty\)。最大流即为答案。
最大流不好计算，考虑最小割。不妨令选取容器集合为 \(S\)，不被 \(S\) 包含的区间都必须割掉，于是代价为 \(\sum\limits_{x\in S}a_x+\sum\limits_{i=1}^m[[l_i,r_i]\nsubseteq S]c_i\) 。
这个可以考虑 dp，\(f_{i,j}\) 表示考虑前 \(i\) 个容器，最后一个未选的为 \(j\)，最小代价。转移类似 AT_dp_w，可以线段树维护做到单次 \(O(n\log n)\)。
考虑 \(t_i=1\) 怎么算。可以发现，此时 \(S\) 可以表示为一个区间 \([L,R]\) 且满足 \(L\le x\le R\)。对 \(L\) 扫描线，维护历史 \(\min\) 即可。
现在存在 \(t_i=0\)，仍然考虑取出 \(S\) 中极大的区间 \([L,R]\) 满足 \(L\le x\le R\)。那么代价可以拆成 \([1,L-1],[L,R],[R+1,n]\) 三个区间的贡献。前缀可以用上面的 dp 预处理 \(F_i\)，后缀同理，记为 \(G_i\)。
中间部分考虑分讨 \(t=0\) 还是 \(1\)：
- \(t_i=0\)：\([l_i,r_i]\) 与 \([L,R]\) 有交且不被包含时被计入代价；
- \(t_i=1\)：\([l_i,r_i]\) 只要不包含于 \([L,R]\) 即可。
这两个部分都可以扫描线，线段树维护历史 \(\min\)，可以做到 \(O(n\log n)\)。
code
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define ls (o << 1)
#define rs (o << 1 | 1)
using namespace std;
void file() {
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
}
using ll = long long;
const ll kInfl = 1e18, kInf = 1e9;
const int kN = 2e5 + 5, kS = 1e6 + 5;
int n, m;
array<int, kN> a;
array<ll, kN> prea, ans;
struct Bot {
int l, r, c, type;
Bot() { }
};
array<Bot, kN> bot;
namespace TYPE0 {
namespace SGT {
array<ll, kS> tag, mn;
void clear() {
fill_n(tag.data(), 4 * (n + 10), 0);
fill_n(mn.data(), 4 * (n + 10), kInfl);
}
void pu(int o) { mn[o] = min(mn[ls], mn[rs]); }
void ad(int o, ll v) { mn[o] += v; tag[o] += v; }
void pd(int o) {
if(ll& x = tag[o])
ad(ls, x), ad(rs, x), x = 0;
}
void modify(int o, int l, int r, int x, ll v) {
if(l == r) return void(mn[o] = v);
pd(o); int mid = (l + r) >> 1;
if(mid < x) modify(rs, mid + 1, r, x, v);
else modify(ls, l, mid, x, v);
pu(o);
}
void update(int o, int l, int r, int x, int y, ll v) {
if((l > y) || (r < x)) return ;
if((l >= x) && (r <= y)) return ad(o, v);
pd(o); int mid = (l + r) >> 1;
update(ls, l, mid, x, y, v);
update(rs, mid + 1, r, x, y, v);
pu(o);
}
ll query() { return mn[1]; }
}
array<ll, kN> F, G;
void clear() {
fill_n(F.data(), n + 2, kInfl);
fill_n(G.data(), n + 2, kInfl);
}
void solvef() {
sort(bot.data() + 1, bot.data() + m + 1, [&](Bot x, Bot y) { return x.r < y.r; });
F[0] = 0;
SGT::clear(), SGT::modify(1, 0, n, 0, 0);
for(int i = 1, j = 1; i <= n; i++) {
ll val = SGT::query();
SGT::modify(1, 0, n, i, val);
SGT::update(1, 0, n, 0, i - 1, a[i]);
for(; (j <= m) && (bot[j].r == i); j++)
if(!bot[j].type)
SGT::update(1, 0, n, bot[j].l, i, bot[j].c);
F[i] = SGT::query();
}
}
void solveg() {
sort(bot.data() + 1, bot.data() + m + 1, [&](Bot x, Bot y) { return x.l > y.l; });
G[n + 1] = 0;
SGT::clear(), SGT::modify(1, 1, n + 1, n + 1, 0);
for(int i = n, j = 1; i; i--) {
ll val = SGT::query();
SGT::modify(1, 1, n + 1, i, val);
SGT::update(1, 1, n + 1, i + 1, n + 1, a[i]);
for(; (j <= m) && (bot[j].l == i); j++)
if(!bot[j].type)
SGT::update(1, 1, n + 1, i, bot[j].r, bot[j].c);
G[i] = SGT::query();
}
}
void solve() { clear(), solvef(), solveg(); }
}
namespace TYPE_ALL {
namespace A {
array<ll, kN> dif;
void clear() { fill_n(dif.data(), n + 1, 0); }
void solve() {
clear();
ll sum1 = 0;
for(int i = 1; i <= m; i++)
if(bot[i].type) sum1 += bot[i].c;
else {
dif[bot[i].l] += bot[i].c;
dif[bot[i].r + 1] -= bot[i].c;
}
for(int i = 1; i <= n; i++) dif[i] += dif[i - 1];
for(int i = 1; i <= n; i++)
ans[i] = dif[i] + sum1 + TYPE0::F[i - 1] + TYPE0::G[i + 1];
}
}
namespace B {
namespace SGT {
struct Info {
ll mn, h;
Info() { mn = h = kInfl; }
Info(ll _mn, ll _h) { mn = _mn; h = _h; }
};
Info operator + (const Info& x, const Info& y) {
return Info(min(x.mn, y.mn), min(x.h, y.h));
}
struct Tag {
ll a00, a01, a11;
Tag() { a00 = a11 = 0; a01 = kInfl; }
Tag(ll _a00, ll _a01, ll _a11) {
a00 = _a00; a01 = _a01; a11 = _a11;
}
bool empty() { return !a00 && !a11 && (a01 == kInfl); }
};
Tag& operator += (Tag& x, const Tag& y) {
Tag ans;
ans.a00 = x.a00 + y.a00;
ans.a01 = min(x.a00 + y.a01, x.a01 + y.a11);
ans.a11 = x.a11 + y.a11;
return x = ans;
}
Info& operator += (Info& x, const Tag& y) {
x.h = min(x.mn + y.a01, x.h + y.a11);
x.mn += y.a00;
return x;
}
array<Info, kS> sum;
array<Tag, kS> tag;
void clear() {
fill_n(sum.data(), 4 * (n + 10), Info());
fill_n(tag.data(), 4 * (n + 10), Tag());
}
void pu(int o) { sum[o] = sum[ls] + sum[rs]; }
void build(int o, int l, int r, ll* val) {
if(l == r)
return void(sum[o] = Info(val[l], val[l]));
int mid = (l + r) >> 1;
build(ls, l, mid, val);
build(rs, mid + 1, r, val);
pu(o);
}
void ad(int o, const Tag& t) { sum[o] += t; tag[o] += t; }
void pd(int o) {
if(!tag[o].empty())
ad(ls, tag[o]), ad(rs, tag[o]), tag[o] = Tag();
}
void update(int o, int l, int r, int x, int y, Tag t) {
if((l > y) || (r < x)) return ;
if((l >= x) && (r <= y)) return ad(o, t);
pd(o); int mid = (l + r) >> 1;
update(ls, l, mid, x, y, t);
update(rs, mid + 1, r, x, y, t);
pu(o);
}
ll query(int o, int l, int r, int x, int y) {
if((l > y) || (r < x)) return kInfl;
if((l >= x) && (r <= y)) return sum[o].h;
pd(o); int mid = (l + r) >> 1;
return min(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
}
void add(int l, int r, ll v) { update(1, 1, n, l, r, Tag(v, kInfl, 0)); }
void updateh() { ad(1, Tag(0, 0, 0)); }
}
array<ll, kN> val;
array<vector<int>, kN> buc0L, buc0R, buc1;
void clear() {
SGT::clear();
fill_n(val.data(), n + 1, 0);
fill_n(buc0L.data(), n + 1, vector<int> ());
fill_n(buc0R.data(), n + 1, vector<int> ());
fill_n(buc1.data(), n + 1, vector<int> ());
}
void init() {
for(int i = 1; i <= m; i++) {
if(!bot[i].type) {
if(bot[i].l != bot[i].r) {
val[bot[i].l] += bot[i].c;
val[bot[i].r] -= bot[i].c;
buc0L[bot[i].l].push_back(i);
buc0R[bot[i].r].push_back(i);
}
}else {
val[1] += bot[i].c;
val[bot[i].r] -= bot[i].c;
buc1[bot[i].l].push_back(i);
}
}
for(int i = 1; i <= n; i++) val[i] += val[i - 1];
for(int i = 1; i <= n; i++)
val[i] += prea[i] + TYPE0::G[i + 1];
SGT::build(1, 1, n, val.data());
}
void solve() {
clear(), init();
for(int i = 1; i <= n; i++) {
ans[i] = min(ans[i], SGT::query(1, 1, n, i, n));
SGT::add(i + 1, n, -a[i]);
for(int j : buc0L[i]) SGT::add(bot[j].r, n, bot[j].c);
for(int j : buc0R[i]) SGT::add(i + 1, n, -bot[j].c);
for(int j : buc1[i]) SGT::add(bot[j].r, n, bot[j].c);
SGT::add(i + 1, n, TYPE0::F[i] - TYPE0::F[i - 1]);
SGT::updateh();
}
}
}
void solve() { A::solve(), B::solve(); }
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i], prea[i] = prea[i - 1] + a[i];
for(int i = 1; i <= m; i++)
cin >> bot[i].l >> bot[i].r >> bot[i].c >> bot[i].type;
TYPE0::solve(), TYPE_ALL::solve();
for(int i = 1; i <= n; i++)
cout << ans[i] << " \n" [i == n];
}
int main() {
// file();
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}