[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)

发布于 15 天前  24 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)

Description

给定一,个长度为n的正整数序列a,每个数都在1到$10^9$范围内,告诉你其中s个数,并给出m条信息,每条信息包含三个数l,r,k以及接下来k个正整数,表示$a[l],a[l+1],...,a[r-1],a[r]$里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大(严格大于,即没有等号)。请任意构造出一组满足条件的方案,或者判断无解。

Tag

差分约束,线段树,拓扑

解决思路

-
题目中给出是若干点大于另外一些点的限制,那么也就是一些点大于等于另一些点+1。按照差分约束的思想,对于x>y,连边y->x,边权为1
但是这样连边是O(n^2)的。对于区间[l,r]中的k个点,把这个区间最多分成k+1个区间。从区间着手,我们可以想到用线段树优化连边。
具体来说,对于每一组(l,r,k),新建一个点node,从node分别向这k个点连权为1的边,表示这k个点比这个新建点大。那么接下来的任务就是把剩下的(r-l+1)-k个点连到node上,权为0。考虑到区间,所以在把每一个区间拆分成log个放到线段树上,从这些线段树上的点引边到node。注意,线段树的点也要连边,即从儿子向父亲连权为0的边
那么,用拓扑排序求一边,得到每一个点的权值下界。无解有三种情况,一是出现环,无法完成拓扑;二是某个点本来给定了权值,但这个给定的权值比得到的下界还要小,这时也无解;三是注意到题目中给出的值域要求在1e9内,所以若出现某个下界大于1e9,则也无解。

代码

-

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)


HNCJ OIer 一枚