d11.4t4 answer
题目
题目描述
小 ∗ 有一条地铁线路。
有 \(n\) 个嘟嘟要乘坐地铁。第 \(i\) 个嘟嘟会在第 \(l_i\)站上车，第 \(r_i\) 站下车。为了方便，我们假定有 \(2n\) 个地铁站，且 \(l_i\) ， \(r_i\) 互不相同。
小 ∗ 很坏，所以只有两班地铁。地铁非常拥挤，所以只有最后上车的嘟嘟才能下车，也就是每班地铁是一个栈。
请你帮每个嘟嘟决定一下上哪班地铁，使得每个嘟嘟都能够成功在目标车站下车。为了方便，数据保证有解。
思路
看到两个栈，想到经典题目双栈排序，即二分图染色。
考虑该题的约束条件，若出现两个嘟嘟交叉的情况，则这两个嘟嘟不能再同一个栈，将这两个点间连一条边约束其不同色即可。
条件即为 \(l1\le l2 \and l2 \le r1 \le r2\) 如下图所示：
如果暴力找前面的点，暴力连边，即可做到 \(O(n^2)\) 的复杂度。
考虑优化。若只有 $l2\le r1 \le r2 $ 的条件，用线段树优化建图即可。
如何去掉第一维？若直接排序，建图是离线操作，没有用。
于是考虑使用可持久化线段树，即可正常去掉第一维。
然而算一算空间复杂度，本题空间只有 \(256\) MB，完全开不了可持久化线段树和线段树优化建图。
考虑问题本质。让 \(a_1,a_2,a_k\) 与 \(i\) 不同色，即让 \(a_1,a_2,a_k\) 同色，再让 \(i\) 与其中任意一个不同色。
则问题转化为：当前一个线段的右端点 \(r\) 排序的序列，支持区间连边(推平)、插入单点的操作。
可以使用类似珂朵莉树的操作，区间推平即直接合并区间，插入单点时分裂区间，并在两区间间连一条边。
最后对于每个连续段，给每个点间依次连边。
分裂操作、标记不同色、最后连边的次数都是 \(O(n)\) 的，因此空间复杂度线性。
对于时间复杂度，可以用vector维护一个区间内点下标，启发式合并可以做到 \(O(n \log n)\) ；也可以使用FHQ维护，复杂度也是 \(O(n\log n)\) 。