Ezzat and Grid(dp/线段树)

题目 题意：给定一个 n ∗ 1 0 9 n*10^9 n∗109的点阵，现在给出m个线段，线段 i , l , r i,l,r i,l,r表示第 i i i行区间 [ l , r ] [l,r] [l,r]取1。现在最少需要删去多少行，才能使得剩下的行中，任何相邻的两行，都至少有一个共同的列，取值都为1。 官方题解 思路：思考最多能保留多少行。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示从第1行到第i行，对于列j来说，能保留的最多行数。则有 d p [ i ] [ j ] = 1 + m a x ( d p [ i − 1 ] [ k ] ) , k ∈ C i , i f g r i d [ i ] [ j ] = 1 dp[i][j] = 1 + max(dp[i-1][k]), k \in C_i, if grid[i][j]=1 dp[i][j]=1+max(dp[i−1][k]),k∈Ci​,ifgrid[i][j]=1 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] , i f g r i d [ i ] [ j ] ≠ 1 dp[i][j] = dp[i-1][j], if grid[i][j]\neq1 dp[i][j]=dp[i−1][j],ifgrid[i][j]​=1 维护区间的最大值，可以用线段树。由于列范围比较大，需要进行下标压缩。 由于答案要求输出具体删除的行，我们可以用pre数组保存dp状态。详见参考代码。 细节比较多，考察的点也多。太懒了没打代码（其实是太菜了） 代码

#define  _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;
#define ONLINE_JUDGE
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout