[CCO 2019]Sirtet

前言

我不明白，这题完完全全是按模拟的思路来做的，为什么有人说它的本质是做差分约束的Dijkstra？不应该差分约束Dijkstra的本质是做模拟才对吗？

题解

首先考虑暴力的模拟怎么做，正常的思路应该是让所有没有接触地面的刚体同时向下移动，直到某一个刚体接触地面，然后把接触地面的刚体视作地面，再让其余刚体继续下落。暴力模拟的复杂度是 O ( n 2 m ) O(n^2m) O(n2m) 的。

想一想怎么加速这个过程。把连通的刚体用并查集缩为一个点，然后考虑每个#下面最近的#。我们把每个#对应的连通块向下面最近的#对应的连通块连边（有向边），特别地，如果下面是地面就向地面连边，边的长度为两个#之间的距离或#到地面的距离。边的数量显然最多是 n m nm nm 数量级的。

不妨先记录一下连向每个连通块的所有边以及连向地面的所有边，这可能是很有用的信息。我们分析一下暴力模拟的过程，每次下落，连通块与连通块之间的边的长度不会变，而连向地面的每条边长度减1。直到其中一条边长度为0的时候这条边的起点对应的连通块就会接触地面。第一条长度为0的边其实就是连向地面的长度最短的边，所以我们可以先把所有连向地面的边放进一个堆里面，然后取出最短的边，把对应连通块加进“地面”，就可以加速这个过程。

在这个过程中，其它连向地面的边的长度都会减去最短的边的长度，同时，连向这个被算作地面的连通块的边，会成为新的一批连向地面的边。我们想要同时快速维护这两者，只需要打一个带懒标记的可并堆即可。每个块都用可并堆维护一个边集，把原先的连向地面的边打上懒标记后，再把块上的可并堆合并进来即可。我们在模拟的同时记录一下每个连通块下落的距离，就可以把原图每个#挪到正确位置。

每次取出和合并必定会减少一条边，所以总复杂度最多 O ( n m log ⁡ n m ) O(nm\log nm) O(nmlognm)。这个复杂度跑不到上界，而且即使加了懒标记，可并堆常数仍然非常小。

代码

#include<cstdio>//JZM yyds!!
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<random>
#define ll long long
#define uns unsigned
#define MOD
#define MAXN 1000005
#define INF 1e18
#define IF it->first
#define IS it->second
using namespace std;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0)f^=(s=='-'),s=getchar();
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
inline void print(int x){
	if(x<0)putchar('-'),print(-x);
	else{
		if(x/10>0)print(x/10);
		putchar(x%10+'0');
	}
}
inline ll lowbit(ll x){return x&-x;}

struct itn{
	int sn[2],a,d,lz;itn(){}
	itn(int A,int D){
		a=A,d=D,sn[0]=sn[1]=0,lz=0;
	}
}t[MAXN];
int IN,rt[MAXN],root;
inline bool cmp(int a,int b){return a>b;}
inline void cover(int x,int d){
	if(!x||!d)return;
	t[x].lz+=d,t[x].a-=d;
}
inline void pushd(int x){
	if(!x||!t[x].lz)return;
	cover(t[x].sn[0],t[x].lz);
	cover(t[x].sn[1],t[x].lz);
	t[x].lz=0;
}
mt19937 Rand;
inline int mergh(int x,int y){
	if(!x||!y)return x^y;
	pushd(x),pushd(y);
	if(cmp(t[x].a,t[y].a))swap(x,y);
	bool o=Rand()%2;
	if(!t[x].sn[o^1])o^=1;
	t[x].sn[o]=mergh(t[x].sn[o],y);
	return x;
}

char s[MAXN],as[MAXN];
int n,m,fa[MAXN],ds[MAXN],drp[MAXN];
bool dpd[MAXN];
inline int finds(int x){
	return fa[x]==x?x:(fa[x]=finds(fa[x]));
}
inline void unions(int x,int y){
	int u=finds(x),v=finds(y);
	if(u^v)fa[v]=u;
}
signed main()
{
	Rand.seed(*new(int));
	n=read(),m=read();
	for(int i=0;i<n*m;i++)fa[i]=i;
	for(int i=0;i<n;i++)scanf("%s",s+i*m);
	for(int i=1;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i*m+j]=='#'){
				if(s[(i-1)*m+j]=='#')
					unions((i-1)*m+j,i*m+j);
			}
	for(int i=0;i<n;i++)
		for(int j=1;j<m;j++)
			if(s[i*m+j]=='#'){
				if(s[i*m+j-1]=='#')
					unions(i*m+j-1,i*m+j);
			}
	for(int i=n-2;~i;i--)
		for(int j=0;j<m;j++){
			if(s[(i+1)*m+j]=='#')ds[i*m+j]=0;
			else ds[i*m+j]=ds[(i+1)*m+j]+1;
		}
	for(int i=n-1;~i;i--)
		for(int j=0;j<m;j++){
			if(s[i*m+j]=='.')continue;
			int u=i*m+j,vi=i+ds[u]+1;
			if(vi>=n){
				t[++IN]=itn(ds[u],finds(u));
				root=mergh(root,IN);
			}else{
				int v=finds(vi*m+j);
				t[++IN]=itn(ds[u],finds(u));
				rt[v]=mergh(rt[v],IN);
			}
		}
	ll ad=0;
	while(root){
		int u=root;pushd(root);
		root=mergh(t[root].sn[0],t[root].sn[1]);
		if(dpd[t[u].d])continue;
		ad+=t[u].a,dpd[t[u].d]=1,drp[t[u].d]=ad;
		cover(root,t[u].a);
		root=mergh(root,rt[t[u].d]);
	}
	for(int i=n*m-1;~i;i--)as[i]='.';
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i*m+j]=='#'){
				int u=finds(i*m+j);
				as[(i+drp[u])*m+j]='#';
			}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)putchar(as[i*m+j]);
		putchar('\n');
	}
	return 0;
}