P4794 [BalticOI 2018]交流电

· · 题解

首先有一个无解的充分条件：有一条线段只被所有区间覆盖一次

接下来让我们考虑对于所有 l_i\le r_i 的情况。

首先，一种染色方案不合法当且仅当覆盖某个线段的区间全部为红或蓝。我们构造方案时可以不改变正确性地要求任意红色区间改变为蓝色区间后都不合法。那么红色区间有 l_i<l_{i+1},r_i<r_{i+1}，任何一条线段至多被红色区间覆盖两次。我们可以维护当前红色区间集合，每次加入一条线段要求依然满足上述限制并且他们的交区间中线段不能有只被覆盖 2 次的（这样就没有蓝区间覆盖它）。这个容易用线段树解决。

对于环上的情况，我们可以钦定一条不被包含的区间为红色。这个区间内如果有只被覆盖 2 次的线段，那么覆盖这个线段的另一个区间必然为蓝色。剩下来的区间就可以映射到破环为链的序列上做 l_i\le r_i 了。