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

发布于 2018-05-07  228 次阅读


本文章由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