题解

51nod Marathon 18 F

考虑从左到右枚举左端点$i$，维护一个数组$f_j$表示左端点$\leq i$时，右端点$\leq j$时候的答案。
考虑每个左端点$i$对应的区间$[l _ i, r _ i]$，考虑暴力算贡献的话，那么就是区间$[l _ i, r _ i]$做一次$f _ j = \max(f _ j, f _ {j - 1} + 1)$，后面$f _ j = \max(f _ j, f _ {j - 1})$。
那么这样我们就可以维护每个$f$相等的段，我们加入了新点的贡献后，区间中内部包含的相等的段长时不会变的，变的只有边界上的两个相等的段，那么这样我们就可以维护了，考虑用差分会好维护一些。