题意
有(n)个不交叉的线段，每个线段有一个权值。现选取一些线段，求每个小区间([i,i+1])至多被覆盖(1-n)次的最大权值和。
思路
- 由于线段互不相交，加上一个([1,10^6])的权值为0的的线段，就可以构成一棵树。
- 可以想到一个(O(n^2))的(dp)，(dp[u][i])代表u这颗子树最多被覆盖(i)次的答案，有状态转移方程(dp[u][i]=max{w_u+sum dp[v][i-1],sum dp[v][i]})。
- 令(f_u(i)=dp[u][i])，可以发现(f)是单调不降函数，且是上凸函数。考虑不取(u)的情况，则(f_{v1}+f_{v2})还是单调不降的上凸函数。取(u)的的情况相当于取(f_u)和向量((1,w_u))的闵可夫斯基和，结果同样还是一个单调不降的上凸函数。
- 可以用堆维护(dp)值的差分，可以发现(f_{v1}+f_{v2})的差分值就是差分由大到小对应位置相加，(f_u(i)=max{f_u(i),f_u(i-1)+w_u})可以看成把(w_u)插入堆中。其中堆合并可以把小的堆并入大的堆中，启发式合并复杂度为(O(nlog^2n))。
- 其真正复杂度为(O(nlogn))的。对于每个节点，都会向堆中插入一个新的数。对于每次堆合并，都是把小的堆的所有节点删除，总大小还是大的堆的大小，没有增加新的元素。所以最多插入(O(n))个元素，删除(O(n))个元素，复杂度为(O(nlogn))。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2.5e5+5;
struct Edge{
int v,next;
}edge[maxn*2];
int head[maxn],ecnt;
void add(int u,int v){
edge[ecnt]={v,head[u]};
head[u]=ecnt++;
edge[ecnt]={u,head[v]};
head[v]=ecnt++;
}
struct Node{
int l,r;
ll val;
}a[maxn];
priority_queue<ll>q[maxn];
void dfs(int u,int f)
{
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v==f)continue;
dfs(v,u);
if(q[u].empty())
swap(q[u],q[v]);
else
{
vector<ll>tmp;
if(q[u].size()<q[v].size())
swap(q[u],q[v]);
while(!q[v].empty())
{
tmp.push_back(q[v].top()+q[u].top());
q[u].pop();
q[v].pop();
}
for(ll val:tmp)
q[u].push(val);
}
}
q[u].push(a[u].val);
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
memset(head,-1,sizeof(head[0])*(n+5));
ecnt=0;
for(int i=0;i<n;i++)
cin>>a[i].l>>a[i].r>>a[i].val;
a[n].l=1;a[n].r=1e6;a[n].val=0;
sort(a,a+n+1,[](Node x,Node y){
if(x.l!=y.l)return x.l<y.l;
else return x.r>y.r;
});
stack<int>stk;
stk.push(0);
for(int i=1;i<=n;i++)
{
int f=stk.top();
while(a[i].l<a[f].l || a[i].r>a[f].r)
{
stk.pop();
f=stk.top();
}
add(i,f);
stk.push(i);
}
dfs(0,-1);
ll ans=0;
for(int i=1;i<=n;i++)
{
if(!q[0].empty())
{
ans+=q[0].top();
q[0].pop();
}
cout<<ans<<(i==n?'
':' ');
}
return 0;
}