[JSOI2019]精准预测

我们先考虑直接按题目上的来建边((2-sat))。
(l(i,j))代表(i)这个点在(j)时活着。
(d(i,j))代表(i)这个点在(j)时死去。
所以对应边来连就行了。
还有第三类边即不能前面死了,后面复活。
但这样的点是(O(Tn))的,我们根本无法接受。
但是我们发现,每条边,标记了(4)个关键点。
我们只要有这些关键点来做题就行了。
那么这样就可把点优化到(O(4m))个。
那怎么统计答案呢。
首先对于(x),统计是否能从(l(x,T + 1))到达(d(x,T + 1)),如果可以那么他是无解的。
否则统计能到达多少个(d(y,T + 1)),答案为(n - cnt - 1).
那么我们只需要来统计可达性问题即可。
(bitset)可以减小复杂度,但我们发现好像不太行。
我们考虑分块来做。
代码鸽了(没睡好呜呜,(bitset)做可达性的话,后面会有一些其他题目)

原文地址:https://www.cnblogs.com/dixiao/p/14833223.html