[ARC069F] Flags

Little09 · 2023-05-25 21:37:40 · 题解

典中典题，但是别写线段树优化建图了，常数很大。

先二分答案，那么就变成了 2-SAT 问题，但是边数是 O(n^2) 的。建边规则是每个点向一个区间内的点连边。

直接 kosaraju，只需要在原图和反图上实现 DFS 过程就行。暴力 DFS 复杂度还是不对，考虑怎么不访问到已经访问的点，用一个并查集维护每个点是否被访问，那么容易找到区间内第一个没被访问的点。

复杂度是 O(n\log n\log v)，其中 \log n 是区间上并查集的复杂度，也可以加个启发式合并得到 \alpha(n)。这样常数很小，在 AT 上可以得到次优解，比线段树优化建图和分块优化建图高明多了。