启发式合并

启发式合并顾名思义就是得到启发后进行合并.
把原本合并时的(n>m) O(nlogm)->O(mlogn).本题题意那么长,说白了就是给你n段,然后询问在所有段最多重叠k次可以的最大权值是多少.
直接建树分治合并即可~
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+56;
typedef long long ll;
struct FZ{
    int l,r;
    ll w;
}tr[N];

bool cmp(FZ a,FZ b)
{
    if(a.l==b.l)    return a.r>b.r;
    else            return a.l<b.l;
}

ll ans[N];//单纯的存下答案而已.
multiset<ll,greater<ll> >s[N];//s[i] 表示i管辖的区域内线段合并的第i大的值.
vector<int>x[N],y;//x[i]表示i的子节点.y当个临时变量存节点的.

void dfs(int u)//进行启发式合并.
{
    for(auto v:x[u])//合并子节点.
    {
        dfs(v);
        if(s[u].size()<s[v].size()) swap(s[u],s[v]);//把v丢进u进行合并,启发式合并.
        multiset<ll,greater<ll> >S;
        for(auto t:s[v])
        {
            ll start=*s[u].begin();
            S.insert(start+t);
            s[u].erase(s[u].begin());
        }
        for(auto t:S)
        {
            s[u].insert(t);
        }
    }
    if(u)   s[u].insert(tr[u].w);//把自己再丢进去.
}

int main()
{
    int n;
    scanf("%d",&n);
    tr[0].l=-1e9,tr[0].r=1e9;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%lld",&tr[i].l,&tr[i].r,&tr[i].w);
    }sort(tr,tr+1+n,cmp);
    y.push_back(0);
    for(int i=1;i<=n;i++)//建树
    {
        while(tr[y.back()].r<tr[i].r)    y.pop_back();
        x[y.back()].push_back(i);
        y.push_back(i);
    }dfs(0);
    int id=0;
    for(auto x:s[0])    ans[++id]=x;
    for(int i=1;i<=n;i++)   ans[i]+=ans[i-1];
    for(int i=1;i<=n;i++)   printf("%lld ",ans[i]);
    puts("");
    return 0;
}