题解：P12031 [USACO25OPEN] Forklift Certified P
Rainesxiao
·
·
题解
思路
首先一个矩形A阻挡另一个矩形B当且仅当A的左下端点在B的右上端点的左下角。
那么显然有一个暴力的做法：将阻挡关系作为一条有向边，M=1 就是求拓扑序，M=2 就是删除前面点后当前点入度是否为 0。
该方法复杂度 O(n^2)，瓶颈在于有向边的数量。
我们考虑不建边，用 dfs 来求拓扑序。
由于矩形左下角的矩形是一个一个处理，我们可以用一维线段树：以 x 坐标为下标，y 坐标作为值，每次求 1 \sim x_2 的最小值，如果 \ge y_2 就代表已经删完，否则就删最小值所对应的矩形，然后继续处理。因为每个矩形只删一次，复杂度是 O(n\log n) 的。
## 代码
```
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs ((p<<1)|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int N=2e5+5,inf=0x3f3f3f3f;
struct node{int x1,x2,y1,y2;}a[N];
int T,n,M;
bool del[N],vis[N];
vector<int> ans;
pii tr[N<<2];
pii merge(pii x,pii y){return x.first<y.first?x:y;}
void build(int p,int l,int r){
tr[p]={inf,0};
if(l!=r) build(lson),build(rson);
}
void update(int p,int l,int r,int x,pii v){
if(l==r){tr[p]=v;return;}
x<=mid?update(lson,x,v):update(rson,x,v),tr[p]=merge(tr[ls],tr[rs]);
}
pii query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return tr[p];
if(L<=mid&&R>mid) return merge(query(lson,L,R),query(rson,L,R));
return L<=mid?query(lson,L,R):query(rson,L,R);
}
void dfs(int u){
if(del[u]) return;
if(!vis[u]) update(1,1,2*n,a[u].x1,{inf,0}),vis[u]=1;//删除
pii v=query(1,1,2*n,1,a[u].x2);
if(v.first>=a[u].y2){del[u]=1,ans.push_back(u);return;}
dfs(v.second),dfs(u);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>T>>M;
while(T--){
cin>>n;build(1,1,2*n);ans.clear();
for(int i=1;i<=n;i++){cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;update(1,1,2*n,a[i].x1,{a[i].y1,i}),vis[i]=del[i]=0;}
if(M==1){
for(int i=1;i<=n;i++) if(!del[i]) dfs(i);
for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
}else{
for(int i=1;i<=n;i++){
update(1,1,2*n,a[i].x1,{inf,0});
cout<<(query(1,1,2*n,1,a[i].x2).first>=a[i].y2);
}
}
cout<<"\n";
}
return 0;
}