线段覆盖问题。先将线段以左端点为第一关键字,右端点为第二关键字均升序排序。
设 fif_ifi 为前 iii 条线段的答案,lil_ili 为在线段 iii 前的首条与其不交的线段。
有转移 fi=minj=li+1i−1{fj}+1f_i = min_{j = l_i + 1}^{i - 1}\{f_j\}+1fi=minj=li+1i−1{fj}+1。分别使用线段树维护 {li}\{l_i\}{li} 和 {fi}\{f_i\}{fi}。
是否具有正确性?