NOIP 模拟 $31; m Cover$

题解 (by;zjvarphi)

因为对于所有区间，都只有包含和被包含关系，这就是一个树形结构。

设 ( m f_{i,j}) 表示在第 ( m i) 个节点，最多被覆盖 ( m j) 次的答案，方程显然。

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