题解 \(by\;zj\varphi\)
因为对于所有区间，都只有包含和被包含关系，这就是一个树形结构。
设 \(\rm f_{i,j}\) 表示在第 \(\rm i\) 个节点，最多被覆盖 \(\rm j\) 次的答案，方程显然。
\[\rm f_{i,j}=\max\{f_{son_i,j-1+a_i}\} \]可以发现，对于一个 \(f_i\) 它的差分数组是单调不增的。
证明：
对于一个 \(f_i\) 如果 \(f_{i,j}-f_{i,j-1}<f_{i,j+1}-f_{i,j}\) 那么，我们就可以把给 \(f_{i,j+1}\) 造成贡献的数转移给 \(f_{i,j}\)。
实现过程就是用一个 \(multiset\) 维护一下即可。
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
ri f=1;x=0;register char ch=gc();
while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x=f?x:-x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define pb(x) push_back(x)
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=3e5+7;
int st[N],n,tp,cnt;
ll ans;
struct Seg{int l,r,w;}seg[N];
inline bool operator<(const Seg &s1,const Seg &s2) {return s1.l==s2.l?s1.r>s2.r:s1.l<s2.l;}
std::multiset<ll> dp[N];
std::vector<int> G[N];
inline void merge(std::multiset<ll> &a,std::multiset<ll> &b) {
if (a.size()<b.size()) std::swap(a,b);
std::vector<ll> tmp;
for (auto x:b) {
tmp.pb(x+*a.begin()),a.erase(a.begin());
}
for (auto x:tmp) a.insert(x);
}
void dfs(int x) {
for (auto v:G[x]) {
dfs(v);
merge(dp[x],dp[v]);
}
dp[x].insert(-seg[x].w);
}
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
cin >> n >> n;
for (ri i(1);i<=n;p(i)) cin >> seg[i].l >> seg[i].r >> seg[i].w;
std::sort(seg+1,seg+n+1);
tp=1;
for (ri i(1);i<=n;p(i)) {
while(st[tp]&&seg[st[tp]].r<seg[i].r) --tp;
G[st[tp]].pb(i);
st[p(tp)]=i;
}
dfs(0);
for (auto x:dp[0]) {
ans-=x,p(cnt),printf("%lld ",ans);
if (cnt==n) break;
}
for (ri i(cnt+1);i<=n;p(i)) printf("%lld ",ans);
puts("");
return 0;
}
}
int main() {return nanfeng::main();}