自动搬运

查看原文

来自洛谷，原作者为

	Hell0_W0rld 硬币抛出之后，正逆的转换从未改变。|| 主页链接：https://www.luogu.me/paste/2r0elp1j

搬运于2025-08-24 22:20:28，当前版本为作者最后更新于2024-12-20 20:45:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6405 [COCI2014-2015#2] ŠUMA 题解

tag：可撤销并查集

题目大意

$N\times N$ 方格表，每个格子的数值初始时 $h_{i,j}$，增长速度为每秒 $v_{i,j}$。求某一个时刻（可以为小数）的最大的相同数字构成的连通块大小。

解题思路

首先我们显然只需要关心相邻格子是否某一个时刻高度相同。

设两个相邻格子 $(x_1,y_1)$ 和 $(x_2,y_2)$。分以下两种情况讨论：

1. $h_{x_1,y_1}=h_{x_2,y_2}$，且 $v_{x_1,y_1}=v_{x_2,y_2}$。这种情况下，无论哪个时刻这两个格子总是在同一个连通块内。可以用普通并查集直接合并在一起。
2. $(x_1,y_1)$ 永远追不上 $(x_2,y_2)$ 或永远不能被 $(x_2,y_2)$ 追上。这种情况下，这对相邻格是废掉的，不用管它。
3. 其他情况下，记录追上的时间和追上的两个格子。

现在，我们已经有了一个关键事件列表，只需要排序后用可撤销并查集将所有的同一时间发生的“高度相同”的事件用可撤销并查集合并，合并时答案对并查集大小取 max 即可。

每一个时间点做完之后，再利用可撤销并查集的特性全部撤销即可。

代码中使用同一个并查集，用是否记录副本的方式同时实现可撤销并查集和并查集。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,l,r) for(register ll i=(l);i<=(r);++i)
#define Rep(i,l,r) for(register ll i=(r);i>=(l);--i)
#define all(x) x.begin(),x.end()
#define rp(i,j,a,b) rep(i,1,a)rep(j,1,n)
using namespace std;
const ll N=709,M=2e6;
ll n,h[N][N],v[N][N];
struct HstInfo{
	ll*addr;
	ll cpy;
} hstP[M],hstSZ[M];
ll nH,ans;
struct Node{
	ll p,sz;
} tr[M];
ll root(ll x){
	return tr[x].p==x?x:root(tr[x].p);
}
ll unite(ll u,ll v,bool isR){
	u=root(u);
	v=root(v);
	if(u==v)return 0;
	if(tr[u].sz>tr[v].sz)swap(u,v);
	if(isR){
		++nH;
		hstP[nH]=(HstInfo){&tr[u].p,tr[u].p};
		hstSZ[nH]=(HstInfo){&tr[v].sz,tr[v].sz};
	}
	tr[u].p=v;
	tr[v].sz+=tr[u].sz;
	return tr[v].sz;
}
void roll(){
	*hstP[nH].addr=hstP[nH].cpy;
	*hstSZ[nH].addr=hstSZ[nH].cpy;
	--nH;
}
void clr(){
	while(nH)roll();
}
#define id(i,j) (i)*n-n+(j)
struct Event{
	ll id1,id2;
	ll dh,dv;
};
vector<Event> events;
bool cmp(const Event&A,const Event&B){
	return A.dh*B.dv<B.dh*A.dv;
}
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
int main(){
	cin>>n;
	rp(x,y,n,n)cin>>h[x][y]; 
	rp(x,y,n,n)cin>>v[x][y]; 
	rp(x,y,n,n)tr[id(x,y)]=(Node){id(x,y),1};
	rp(x,y,n,n)rep(k,0,1){
		ll nx=x+dx[k], ny=y+dy[k];
		if(nx>n||ny>n)continue;
		ll dh=h[nx][ny]-h[x][y];
		ll dv=v[x][y]-v[nx][ny];
		if(!dv&&!dh)ans=max(ans,unite(id(x,y),id(nx,ny),0));
		else if(dv>0&&dh>=0)events.push_back((Event){id(x,y),id(nx,ny),dh,dv});
		else if(dv<0&&dh<=0)events.push_back((Event){id(nx,ny),id(x,y),-dh,-dv});
	}
	sort(all(events),cmp);
	ll T=events.size();
	rep(i,0,T-1){
		Event &e=events[i];
		ans=max(ans,unite(e.id1,e.id2,1));
		if(i+1<T&&cmp(e,events[i+1]))clr();
	}
	cout<<ans<<endl;
	return 0;
}