「CEOI2019」建造摩天楼
显然是倒着考虑删除每个大楼，此时每次面临的情况都是一个子问题
下文称当前局面未被删除的大楼为黑点，其余为白点
子问题有解的充要条件是：黑点之间能 8-连通
当前一个点能够被删掉的条件是：
1.这个点能够连通到无穷处
2.这个点不是当前8-连通图的割点
[
]
考虑用一个简单的方法维护条件1：
将一开始每个黑点周围的白点取出，按照白点之间4-连通构建连通块
能够4-连通接触到最外层连通块的黑点满足条件1
每次删除黑点之后，增加能够连通的白点，每个白点只会增加一次
ps:寻找最外层4-连通白点的一个方法：找到x最大的白点
[
]
接下来考虑如何判定一个点(u)是否是割点：
首先删除(u)之后，周围8连通内能够构成多个连通块，可以发现大致可以归结为以下几种情况，其中x,y为黑点
多个(x)表示(x)在其中任何一个位置都可以
| 1. | ||
|---|---|---|
| x | ① | y |
| x | u | y |
| x | ② | y |
| 2. | ||
|---|---|---|
| x | ① | y |
| ② | u | y |
| y | y | y |
对于这两种情况，只要白点1和白点2在同一4-连通块，割掉(u)就会分开x和(y)
由此，每次插入一个白点，可以(O(1))检测一个点是否合法
简单讨论可以发现，会被影响合法性的点，一定在新加入最外层连通块的白点周围
这样总共check了(O(n))次，每次用一个堆/set维护能选的最大编号的点即可
ps:代码非常丑非常垃圾。。。
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=1.3e6+10,INF=1e9+10;
const int z[5][4]={{1,0},{0,-1},{-1,0},{0,1}};
const int Z[9][4]={{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1}};
int n,m,k;
int F[N];
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]);}
void Union(int x,int y){ F[Find(x)]=Find(y); }
map <Pii,int> B,W;
set <int> st;
vector <int> ans;
Pii A[N],P[N];
int ma=-1e9,maxid;
int G[N][4];
void Ins(int x,int y){
// Insert white point
Pii T=mp(x,y);
if(B.count(T)) return ;
if(!W.count(T)) P[W[T]=++m]=T,F[m]=m;
int u=W[T];
if(x>ma) ma=x,maxid=u;
rep(i,0,3) {
int x1=x+z[i][0],y1=y+z[i][1];
if(W.count(mp(x1,y1))) {
int v=W[mp(x1,y1)];
G[u][i]=v;
G[v][(i+2)%4]=u;
Union(u,v);
}
}
}
int del[N],vis[N],reach[N];
int Check(int u){
if(del[u]||!reach[u]) return 0;
static int I[8];
int c=0;
rep(i,0,7) {
Pii T=mp(A[u].x+Z[i][0],A[u].y+Z[i][1]);
if(W.count(T)) I[i]=Find(W[T]);
else I[i]=0,c++;
}
for(int i=1,t=0;t<4;t++,i=(i+2)%8){
int j=(i+2)%8;
if(I[i] && I[i]==I[j] && !I[(i+1)%8] && c>1) return 0;
}
if((!I[0]||!I[1]||!I[2]) && (!I[4]||!I[5]||!I[6]) && I[3] && I[3]==I[7]) return 0;
if((!I[2]||!I[3]||!I[4]) && (!I[6]||!I[7]||!I[0]) && I[1] && I[5]==I[1]) return 0;
return 1;
}
void ReCheck(int u){
auto it=st.find(u);
if(it!=st.end()) st.erase(it);
if(Check(u)) st.insert(u);
}
vector <int> tmp;
void dfs(int u){
if(!u) return;
if(vis[u]) return;
vis[u]=1;
rep(i,0,3) {
if(G[u][i]) dfs(G[u][i]);
Pii T=mp(P[u].x+z[i][0],P[u].y+z[i][1]);
if(B.count(T)) reach[B[T]]=1;
}
rep(dx,-1,1) rep(dy,-1,1) if(dx||dy) {
Pii T=mp(P[u].x+dx,P[u].y+dy);
if(B.count(T)) tmp.pb(B[T]);
}
}
void Dfs(int u){
dfs(u);
sort(tmp.begin(),tmp.end()),tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
for(int i:tmp) ReCheck(i);
tmp.clear();
}
void Del(int u){
// delete black point
del[u]=1;
B.erase(A[u]),Ins(A[u].x,A[u].y);
Dfs(W[A[u]]);
}
int main(){
n=rd(),rd();
rep(i,1,n) A[i].x=rd(),A[i].y=rd(),B[A[i]]=i;
rep(i,1,n) F[i]=i;
// Check NO
rep(i,1,n) {
rep(dx,-1,1) rep(dy,-1,1) {
Pii T=mp(A[i].x+dx,A[i].y+dy);
if(B.count(T)) Union(i,B[T]);
}
}
rep(i,1,n) if(Find(i)!=Find(1)) return puts("NO"),0;
rep(i,1,n) rep(dx,-1,1) rep(dy,-1,1) if(dx||dy) Ins(A[i].x+dx,A[i].y+dy);
Dfs(maxid);
rep(i,1,n) {
int u=*st.rbegin();
auto it=st.end(); --it;st.erase(it);
Del(u),ans.pb(u);
}
reverse(ans.begin(),ans.end());
puts("YES");
for(int i:ans) printf("%d
",i);
}