根据ccz181078大爷的题解可得(QAQ,每次肯定是断掉连续一行||一列的栅栏。。。

  贪心地想,一个格子与外面联通,显然是先把短的边界断掉(就像mst那样

  但是比较蛋疼的是,因为我们每次断的时候,有一些点可能已经联通了,所以有的栅栏不用断>_<

  如果我们断了x列栅栏,并且之前有断过行的栅栏,那么下一次断开行的时候,那一行上的联通块个数就是n-x+1。。(假设有n行

  列上的联通块个数同理

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int v;bool id;
}c[maxn<<];
int a[maxn],b[maxn],A,B;
int numh,numl,smh,sml;//numh,numl:当前已连了多少行、列。smh,smhl:每行||列有多少个联通块
int i,j,k,n,m;
ll ans; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool cmp(zs a,zs b){return a.v<b.v;}
int main(){
A=read(),B=read(),n=read(),m=read();
for(i=;i<=n;i++)a[i]=read();a[n+]=A;
for(i=;i<=m;i++)b[i]=read();b[m+]=B;
sort(a+,a++n);sort(b+,b++m);
n++,m++;
for(i=n;i;i--)c[i].v=a[i]-a[i-],c[i].id=;
for(i=m;i;i--)c[i+n].v=b[i]-b[i-],c[i+n].id=;
sort(c+,c++n+m,cmp);
smh=n,sml=m;j=;
while(smh>||sml>){
j++;//printf(" %d %d\n",sml,smh);
if(!c[j].id)ans+=(ll)(sml-)*c[j].v,numl++;
else ans+=(ll)(smh-)*c[j].v,numh++;
if(numl)sml=min(m,m-numh+);
if(numh)smh=min(n,n-numl+);
// printf(" ans:%lld %d %d\n",ans,(int)c[j].id,c[j].v);
}
printf("%lld\n",ans);
return ;
}
05-11 22:15