E
令 \(m=s/2\)。将 \(r<m\) 的区间称作 A 类,\(m<l\) 的 B 类,\(l\leq m\leq r\) 的 C 类。A、B 类可以互相匹配,过程如下:将 B 翻转,假如 A 类都叫 \([l_i, r_i]\),B 类对称翻转后叫作 \([l_j, r_j]\),将 \(l_i, r_j\) 混合从小到大排序,维护一个升序的 set,遇到 \(l_i\) 时将 \(r_i\) 插入,遇到 \(r_j\) 时二分查找 \(l_j\) 的 lower_bound
,找到的区间可以发现是一定有交的,也发现我们尽量要保留 \(r_i\) 较大的方便后来的 \(j\) 去匹配。匹配不上就放弃,A 类将 \(r_i\)、B 类将 \(l_j\) 这些单点拿出来作为一个集合,与 C 类做匹配,变成了区间与点匹配,再尽可能做这些匹配。最后剩下的 C 类可以互相匹配。