做题记录 25.9.16

· · 个人记录

\purple\odot AT_joisc2017_b 港湾設備 (Port Facility) \quad LOJ #2391. 「JOISC 2017 Day 1」港口设施

对于 i\ne j，若有 a_i<a_j<b_i<b_j，则两者不能在同一栈中

此时在两者之间连边，若最终为二分图则答案为 2^c，其中 c 为连通块数量，否则答案为 0

将所有 (a,b) 按 a 从小到大排序，然后枚举 (a_i,b_i)，转化为 i 向 [a_i+1,b_i-1] 中的值连边，和在 b_i 处插入值 i

考虑用线段树维护之，每个结点保存一个栈，插入操作时在递归到的所有结点处插入值，连边时枚举分割到的每个区间，转化为 i 向该区间内所有值连边

考虑单独一个区间，每次操作为插入一个数，和所有数向 i 连边

假定先后两次连边操作 i,j 都需要连向两个数 a,b，则 j-b 的连边可以省略，且不改变图是否二分

具体地，在栈的基础上，记录一个值 f，表示当前区间中第一个插入的值

每插入一个新的值，若在此之前还没有插入过值，则令 f 为当前插入值，然后将当前值加入栈中

连边时，若 f=0 则返回，否则与 f 和栈中所有值连边，并清空栈

显然时间复杂度 O(n\log n)

代码

参考