一种自认为比较好想、好理解、好写的做法。
题意简述
有 \(n\) 个电站，频率范围是 \(l_i,r_i(1\le l_i\le r_i\le m)\)，有 \(m1\) 条限制形如 \(x,y\)，表示 \(x,y\) 电站至少选一个；同时有 \(m2\) 条限制形如 \(x,y\)，表示 \(x,y\) 电站至多选一个；同时要满足选出的电站的频率范围有交。求解的存在性。
输入格式：第一行四个整数 \(m1,n,m,m2\)，接下来 \(m1\) 行描述限制，接下来 \(n\) 行描述频率范围，接下来 \(m2\) 行描述限制。
输出格式：若无解输出 -1，若有解，第一行分别输出选出电站数量 \(k\) 和选出的电站的频率范围的交集中的任意一个整数元素 \(f\)，第二行以任意顺序输出选出的电站编号。
\(n,m,m1,m2\le 4\times10^5\)。
备注：本文中的 \(n,m,m1,m2\) 分别代表了原题的 \(p,M,n,m\)。
分析
看到这种限制立即想到 2-SAT。
那 \(m1+m2\) 条限制就是纯 2-SAT 板子，不再赘述。
考虑怎么处理区间有交的问题，发现这个限制相当于我们不能选两个无交的区间，但是暴力两两之间连边是 \(O(n^2)\) 的。
发现区间 \([l_i,r_i]\) 与区间 \([l_j,r_j]\) 无交当且仅当 \(r_i<l_j\) 或 \(r_j<l_i\)。而我们发现 \(l_j>r_i\) 的 \(j\) 是一段后缀，\(r_j<l_i\) 的 \(j\) 是一段前缀。
那么做法就呼之欲出了。使用前缀和优化建图（不会前缀和优化建图见 Riddle），每个前缀点 \(pre_i\) 连向以该点为右端点的电站的反点，每个后缀点 \(sec_i\) 连向以该点为左端点的电站的反点。根据定义有连边 \(pre_i\rightarrow pre_{i-1},sec_i\rightarrow sec_{i+1}\)。其次，对于每个点 \(i\)，有连边 \(i\rightarrow pre_{l_i-1},i\rightarrow sec_{r_i+1}\)，注意此时的 \(i\) 为 \(i\) 的正点。
标签：pre,sec,le,电站,Stations,Radio,CF1215F,m2,m1 From： https://www.cnblogs.com/dcytrl/p/18012910