[CSP-S模拟测试]:Cover（单调栈++单调队列+DP）

题目传送门（内部题126）

输入格式

　　第一行两个个整数$n,m$表示区间的长度与彩灯的数量。
　　接下来$m$行，每行三个整数$l_i,r_i,a_i$表示一条彩灯能够覆盖的区间以及它的美观程度。

输出格式

　　输出一行$m$个整数，第$i$个数表示$k=i$时的最大美观程度。

样例

样例输入：

25 6
1 2 10
2 3 10
1 3 21
3 4 10
4 5 10
3 5 19

样例输出：

41 80 80 80 80 80

数据范围与提示

　　对于$25\%$的数据，$m\leqslant 20$
　　对于$45\%$的数据，$n,m\leqslant 5,000$
　　对于另外$25\%$的数据，所有$a_i$相同
　　对于$100\%$的数据，$1\leqslant l_i\leqslant r_i\leqslant n,m\leqslant 300,000,a_i\leqslant 10^9$

题解

因为不能重叠，所以将所有的区间向其覆盖的区间连边，单调栈维护即可。

然后会得到一棵树，对于每一个节点维护一个单调队列更新其父节点答案即可，思想类似树上$DP$。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int id,l,r,a;}s[400001];

struct node{int nxt,to;}e[700001];

int head[400001],cnt;

int n,m;

int now=2;

int size[300001];

long long ans;

priority_queue<long long> q[400001],v;

bool cmp(rec a,rec b){return a.l<b.l||(a.l==b.l&&a.r>b.r)||(a.l==b.l&&a.r==b.r&&a.id>b.id);}

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void build(int x)

{

	while(s[x].l<=s[now].l&&s[now].r<=s[x].r)

	{

		add(x,now);

		now++;

		build(now-1);

	}

}

void dfs(int x)

{

	for(int i=head[x];i;i=e[i].nxt)

	{

		dfs(e[i].to);

		size[x]=max(size[x],size[e[i].to]);

	}

	size[x]++;

	for(int i=head[x];i;i=e[i].nxt)

		if(size[e[i].to]+1==size[x]){swap(q[x],q[e[i].to]);e[i].to=0;break;}

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(e[i].to)

		{

			while(q[e[i].to].size())

			{

				v.push(q[x].top()+q[e[i].to].top());

				q[x].pop();q[e[i].to].pop();

			}

			swap(v,q[x]);

			while(v.size())

			{

				q[x].push(v.top());

				v.pop();

			}

		}

	}

	q[x].push(s[x].a);

}

int main()

{

	scanf("%d%d",&n,&m);n--;

	for(int i=1;i<=m;i++)

	{

		s[i].id=i;

		scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].a);

		s[i].r--;

	}

	s[++m]=(rec){m,1,n,0};

	sort(s+1,s+m+1,cmp);

	build(1);dfs(1);

	for(int i=1;i<=m;i++)q[1].push(0);

	for(int i=1;i<m;i++)

	{

		ans+=q[1].top();

		q[1].pop();

		printf("%lld ",ans);

	}

	return 0;

}

rp++