题解：P6405 [COCI2014-2015#2] ŠUMA
Hell0_W0rld
·
·
题解
P6405 [COCI2014-2015#2] ŠUMA 题解
tag：可撤销并查集
题目大意
### 解题思路
首先我们显然只需要关心相邻格子是否某一个时刻高度相同。
设两个相邻格子 $(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 即可。
每一个时间点做完之后，再利用可撤销并查集的特性全部撤销即可。
代码中使用同一个并查集，用是否记录副本的方式同时实现可撤销并查集和并查集。
### 代码实现
```cpp
#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;
}
```