[bzoj4410] [Usaco2016 Feb]Fence in

　　根据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 ;

 }