CF1557D Ezzat and Grid 题解
Acc_Robin
·
·
题解
CF1557D Ezzat and Grid 题解
传送门
更高更妙的阅读体验
题意
给你一个 n\times m 的 01 串，让你删去最少的行（删去一行之后，上下两行变为相邻）使得任意相邻两行都有至少一个公共的位置上是 1.
### 题解
首先做一步小转化，从“删去最少”变成“选取最多”。
考虑DP，令 $f_{i}$ 表示前 $i$ 行最多选取几行，转移有
$$
f_i=\max_{j<i \land \text{第i行与第j行有公共的1}} f_{j}+1
$$
注意到我们需要处理区间相交的问题，无疑线段树是合适的选择。
我们使用线段树来维护区间最大值：加入第 $i$ 行时，使用线段树求出与第 $i$ 有公共部分的最大值 $f_j,(j<i)$，完成 $f_j$ 到 $f_i$ 的转移之后再将第 $i$ 行有 $1$ 的位置全部更新成 $f_i$。
注意此题还要求输出方案，所以线段树上维护最大值的同时维护一下最大值来自于哪一行。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
namespace Acc{
using pii=pair<int,int>;
const int N=3e5+9;
const pii NUL={0,-1};
int b[N<<1],L[N<<3],R[N<<3],las[N],f;
pii v[N<<3],t[N<<3];
vector<pii>g[N];
#define lc (o<<1)
#define rc (o<<1|1)
void up(pii&x,pii y){if(x<y)x=y;}
void bd(int o,int l,int r){
L[o]=l,R[o]=r,v[o]=t[o]=NUL;
if(l==r)return;
int md=l+r>>1;
bd(lc,l,md),bd(rc,md+1,r);
}
void pd(int o){
if(t[o]==NUL)return;
up(v[lc],t[o]),up(v[rc],t[o]);
up(t[lc],t[o]),up(t[rc],t[o]),t[o]=NUL;
}
pii ask(int o,int l,int r){
if(l<=L[o] && R[o]<=r)return v[o];
pd(o);
int md=L[o]+R[o]>>1;pii z=NUL;
if(l<=md)up(z,ask(lc,l,r));
if(r>md)up(z,ask(rc,l,r));
v[o]=max(v[lc],v[rc]);
return z;
}
void add(int o,int l,int r,pii x){
if(l<=L[o] && R[o]<=r)return (void)(up(v[o],x),up(t[o],x));
int md=L[o]+R[o]>>1;pd(o);
if(l<=md)add(lc,l,r,x);
if(r>md)add(rc,l,r,x);
v[o]=max(v[lc],v[rc]);
}
void work(){
int n,m,l=0,x,y,z,i;
for(cin>>n>>m;m--;)
cin>>x>>y>>z,g[x].push_back({y,z}),b[l++]=y,b[l++]=z;
sort(b,b+l),l=unique(b,b+l)-b,bd(1,1,l);
for(i=1;i<=n;++i)for(auto&[x,y]:g[i])
x=lower_bound(b,b+l,x)-b+1,y=lower_bound(b,b+l,y)-b+1;
for(i=1;i<=n;++i){
pii mx=NUL;
if(i==5)f=1;
for(auto[x,y]:g[i])mx=max(mx,ask(1,x,y));
las[i]=mx.second,mx.second=i,++mx.first;
for(auto[x,y]:g[i])add(1,x,y,mx);
}
pii mx=ask(1,1,l);cout<<n-mx.first<<'\n';
for(x=mx.second;~x;x=las[x])b[x]=-1;
for(i=1;i<=n;++i)if(~b[i])cout<<i<<' ';
}
}
int main(){return Acc::work(),0;}
```
### 小细节
此题的值域较大，需要离散化。