题目大意

给定 $m$ 个区间 $[l_i..r_i]$， 每一个区间都有一个权值 $a_i$， 保证每个区间只有包含与不相交的关系，对于每一个 $k=1,\ 2,\ \cdots,\ m$， 选出若干个区间，使 $[1..n]$ 中的每一个点不被超过 $k$ 个区间覆盖，并求出最大的权值和.
$1\le l_i\le r_i\le m,n\le300000,a_i\le10^9$

思路

注意题目给出的一个条件：

保证每个区间只有包含与不相交的关系

所以这个区间是一个树的关系。
首先建出这个树：将所有的区间按照右端点升序、左端点降序排序（或者其他方式，能建出树就可以），然后每次将区间压入一个栈中，遇到左端点大于栈顶元素的就一定满足包含关系，直接拿出即可。

接下来我们来考虑树形DP：
设 $f_{i,j}$ 表示以 $i$ 为根的子树中被不超过 $j$ 段区间覆盖的最大权值和，那么不难推出以下递推式：

\(f_{i,j}=\max(\sum_{k\in son_i}f_{k,j},\ \sum_{k\in son_i}f_{k,j-1}+a_i)\) 复杂度 $O(m^2)$， 保证会炸
我们可以尝试来优化这个DP。

考虑 $f_{i,j}$ 的差值 $g_{i,j}=f_{i,j}-f_{i,j-1}$， 不难发现 $g_{i,j}$ 是单调不增的，肯定先选最优解，感性理解下
那么我们可以用一个multiset来维护这个 $g_{i,j}$ 然后合并时启发式合并即可。
说这么简单，怎么合并？？？

把这个DP式子可以进行一些转换：

\[\begin{aligned} f_{i,j}&=\max(\sum_{k\in son_i}f_{k,j},\ \sum_{k\in son_i}f_{k,j-1}+a_i)\\ &=\max(\sum_{k\in son_i}\sum_{p=1}^jg_{k,p},\ \sum_{k\in son_i}\sum_{p=1}^{j-1}g_{k,p}+a_i) \end{aligned}\]

那么当 $j$ 增加时， $\max$ 左面的式子每次加 $\sum_{k\in son_i}g_{k,j}$， 右面的式子每次加 $\sum_{k\in son_i}g_{k,j-1}$， 由于 $g_{i,j}$ 是单调不增的，那么 $g_{k,j}\le g_{k,j-1}$， 那么 $\sum_{k\in son_i}g_{k,j}\le \sum_{k\in son_i}g_{k,j-1}$。
也就是说，当枚举到某一个 $j$ 以后，右面的一定会优于左面的，假设这个分界线为 $j$ （$j-1$ 选左面， $j$ 选右面）， 那么我们发现：

\[\begin{aligned} g_{i,j}&=f_{i,j}-f_{i,j-1}\\ &=(\sum_{k\in son_i}\sum_{p=1}^jg_{k,p}+a_i)-\sum_{k\in son_i}\sum_{p=1}^{j}g_{k,p}\\ &=a_i \end{aligned}\]

所以我们只需要把 $a_i$ 也扔进multiset里就可以了。
在其他情况下， $g_{i,j}$ 就等于 $\sum_{k\in son_i}g_{k,j}$ 或者 $\sum_{k\in son_i}g_{k,j-1}$， 两个multiset必然是有序的， 所以直接将两个multiset对应位置相加维护就可以了。

合并时可以用一个启发式合并：其实就是将数比较少multiset的合并到数比较大的multiset，合并也很简单，两个multiset不断取begin，相加扔新multiset就可以了。

结果得到一个multiset，因为是单调递减的，直接从后往前扫一遍，把前 $k$ 个差分加起来就是 $f_{1,k}$ 了。

复杂度 $O($我不会证$)$

反正挺玄学的

注意

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 300005;
struct Node {
    int l,r,a;
}nodes[MAXN];
int n,m;
bool cmp(const Node &a,const Node &b) {
    return a.r!=b.r?a.r<b.r:a.l>b.l;
}
int fa[MAXN],dep[MAXN],son[MAXN];
vector<int> to[MAXN];
multiset<int> dfs2(int i) {
    if (to[i].size()!=0) {
        multiset<int> s;
        multiset<int>::iterator it;
        stack<int> st;
        for(int j : to[i]) {
            multiset<int> p=dfs2(j);
            if(s.size()<p.size()) swap(s,p);
            it=s.begin();
            for(int t : p) {
                st.push(*it+t);
                s.erase(it);
                it++;
            }
            while(!st.empty()) {
                s.insert(st.top());
                st.pop();
            }
        } 
        s.insert(-nodes[i].a);
        return s;
    } else {
        multiset<int> s;
        s.insert(-nodes[i].a);
        return s;
    }
}
signed main() {
    scanf("%lld%lld", &n, &m);
    for(int i=1;i<=m;i++) scanf("%lld%lld%lld", &nodes[i].l, &nodes[i].r, &nodes[i].a);
    sort(nodes+1,nodes+1+m,cmp);
    stack<int> st;
    for(int i=1;i<=m;i++) {
        while(!st.empty() && nodes[st.top()].l>=nodes[i].l) {
            fa[st.top()]=i;
            to[i].push_back(st.top());
            st.pop();
        }
        st.push(i);
    }
    for(int i=1;i<=m;i++) if(!fa[i]) to[0].push_back(i);
    multiset<int> s=dfs2(0);
    int sum=0;
    for(int i=1;i<=m;i++) {
        if (!s.empty()) {
            sum-=*s.begin();
            s.erase(s.begin());
        }
        printf("%lld ", sum);
    }
    return 0;
}