https://codeforces.com/contest/1557
题意：
给出一个(n*10^9)的01矩阵。用(m)个区间表示。（(1 leq n,m leq 3 imes 10^5)）
每个区间包含三个信息：(i,l,r)。表示在第(i)行，第(l)个元素到第(r)个元素是1。
一个矩阵被称为美丽的，当且仅当，这个矩阵任意相邻的两行，存在一列使得这两行都为1。
询问最少要删除几行使得矩阵是美丽的。
输出删除数量最少的一个删除方案。
题解：
我们定义：
(f[i])为在保留第(i)行的前提下，最少删除几行使得前(i)行是美丽的。
(pre[i])为(f[i])表示的状态下，上一个未被删除的行的编号。
那么我们可以枚举(i)之前的行，设我们当前枚举的是(j)，如果第(i)行和第(j)行有某个位置都是1，那么(f[i])可以由(f[j]+i-j-1)转移过来。
换句话说，对于所有满足条件的(j)，我们取(f[j]+i-j-1)的最小值作为(f[i])的答案。
即：(f[i]=min_{j=1}^{i-1}f[j]+i-j-1[行i和行j有一个位置都是1])
然后把这个式子移项，想方设法让(i)和(j)独立：
(f[i]-i=min_{j=1}^{i-1}f[j]-j-1)
观察到式子右边只和(j)有关了。
然后我们考虑如何找满足条件([行i和行j有一个位置都是1])的(j)的数量。
可以先对所有区间([i,l,r])做离散化处理，然后用数组(a)表示两个信息：
(a_i)表示第(i)个点为(1)的所有行的最小(f[j]-j-1)值和对应(j)的值。
用线段树维护数组(a)的区间最小值。
然后在转移的过程中，参考线段树求最长递增子序列的思路，先对当前第(i)行的所有区间，区间询问数组(a)的最小值，然后取最小值和那个对应的下标转移给(f[i])和(pre[i])。然后对第(i)行的所有区间([l,r])，用(f[i]-i-1)去和区间里的值(a_i)取(min)，即对区间内的每个数(a_i)，(a_i=min(a_i,f[i]-i-1))。
对于这部分，懒惰标记有点细节处理：
假设我们要使得区间内(a_i=min(a_i,v))。
1）如果当前区间的最小值大于(v)，就更新当前区间的最小值和下标，同时把懒惰标记往下打。
2）如果当前区间的最小值小于等于(v)，就直接往下打懒惰标记，不修改当前区间的信息。
最后，枚举(f[i]+n-i)的最小值，得到最优答案和最后一个没有被删除的行的位置，根据(pre[i])往前递归求出所有没有被删除的行。
剩下的就是被删除的行，输出即可。