Codeforces Round #737 (Div. 2) Ezzat and Grid（线段树优化dp）_codeforces 线段树优化图论

题目地址：Ezzat and Grid
Moamen was drawing a grid of n rows and 109 columns containing only digits 0 and 1. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.

A grid is beautiful if and only if for every two consecutive rows there is at least one column containing 1 in these two rows.

Ezzat will give you the number of rows n, and m segments of the grid that contain digits 1. Every segment is represented with three integers i, l, and r, where i represents the row number, and l and r represent the first and the last column of the segment in that row.

For example, if n=3, m=6, and the segments are (1,1,1), (1,7,8), (2,7,7), (2,15,15), (3,1,1), (3,15,15), then the grid is:

Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

思路：dp[i][j] 为 i 行之前删除一些行之后满足条件的最大行数， j为这一行中有1的状态
要寻找当前行中满足条件的最大行数 如果当前行中有1的状态和前面行中有1的状态相交 ，当前行=前面与当前1相交的行的最大值 +1
可以用线段树维护区间最大值

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
//const int inf=2e18+100;
const int maxn=1e6+100;
typedef pair<int,int> pii;
struct node//线段树维护区间最大值，顺便保存行号； 
{
   int l,r;
   pii sum;
   pii lazy;
   //int c;
} t[maxn*4];
struct node1
{
   int c,l,r;
} t1[maxn];
vector<pii>g[maxn];
pii Max(pii a,pii b)
{
   if(a.first>b.first)return a;
   return b;
}
void pushup(int k)
{
   t[k].sum=Max(t[k<<1].sum,t[k<<1|1].sum);
}
void pushdown(int k)
{
   if(t[k].lazy.first)
   {
   	t[k<<1|1].lazy=t[k].lazy;
   	t[k<<1].lazy=t[k].lazy;
   	t[k<<1|1].sum=t[k].lazy;
   	t[k<<1].sum=t[k].lazy;
   	t[k].lazy={0,0};
   }
}
void build(int k,int l,int r)
{
   t[k].l=l;
   t[k].r=r;
   if(l==r)return ;
   int mid=(l+r)>>1;
   build(k<<1,l,mid);
   build(k<<1|1,mid+1,r);
   pushup(k);
}
void update(int l,int r,int k,pii p)
{
   if(l>t[k].r||r<t[k].l)return ;
   if(l<=t[k].l&&t[k].r<=r)
   {
   	t[k].sum=p;
   	t[k].lazy=p;
   	return ;
   }
   pushdown(k);
   update(l,r,k<<1,p);
   update(l,r,k<<1|1,p);
   pushup(k);
}
pii query(int l,int r,int k)
{
   if(r<t[k].l||l>t[k].r)return {0,0};
   if(l<=t[k].l&&t[k].r<=r)
   {
   	return t[k].sum;
   }
   pushdown(k);
   return Max(query(l,r,k<<1|1),query(l,r,k<<1));
}
map<int,int>mp;
int pre[maxn];//保存前驱 
bool vis[maxn];
signed main()
{
   IOS
   int n,m;
   cin>>n>>m;
   for(int i=1; i<=m; i++)
   {
   	int c,l,r;
   	cin>>c>>l>>r;
   	mp[l]=1;
   	mp[r]=1;
   	t1[i]= {c,l,r};
   }
   int k=0;
   for(auto it:mp)
   {
   	mp[it.first]=++k;//离散化 
   }
   build(1,1,k);
   for(int i=1; i<=m; i++)
   {
   	int x=mp[t1[i].l];
   	int y=mp[t1[i].r];
   	g[t1[i].c].push_back({x,y});
   }
   int ans=0,fg=0;//最大的值和取得最大值的行 
   for(int i=1; i<=n; i++)
   {
   	int now=-1;
   	for(auto it:g[i])
   	{
   		pii p=query(it.first,it.second,1);//查询i之前该区间的最大值 
   		if(p.first>now)
   		{
   			now=p.first;
   			pre[i]=p.second;
   		}
   	}
   	if(now+1>ans)//更新最大值 
   	{
   		ans=now+1;
   		fg=i;
   	}
   	for(auto it:g[i])
   	{
   		update(it.first,it.second,1, {now+1,i});//更新i行的区间 
   	}
   }
   cout<<n-ans<<"\n";
   for(int i=fg; i != 0; i = pre[i]) vis[i] = 1;
   for(int i=1; i<=n; i++)
   {
   	if(vis[i]==0)
   	{
   		cout<<i<<" ";
   	}
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134