首先我们观察到有一个性质:如果我们把的位置放入集合,的位置放入集合,那么最后一定是选择一个集合元素和一个集合元素进行交换最优秀。
然后我就一直在想,把每个位置转化成二维平面的一个点,然后跑平面最近哈夫曼距离啥的。硬是没想到一个关键的性质:如果把每个位置的都组成一个线段,交换两个位置减少的代价就是线段的交乘二。所以现在问题就转化为了:两个集合分别有一堆线段,然后从两个集合各自拿出一条线段求交,要求交的值最大。
那我们分类讨论,先假设中线段的比较小,那么就对中所有元素建一个下标为,权值为的线段树,然后对于中的每个线段丢进去查找满足条件中,的最大值。这样就能计算出交的大小了,另一种同理。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2e5+100;
const int inf=1e9+10;
struct segment_tree{
int mx[maxn*35],cnt,ls[maxn*35],rs[maxn*35];
segment_tree(){cnt=1;}
void push_up(int rt){mx[rt]=max(mx[ls[rt]],mx[rs[rt]]);}
int ins(int l,int r,int rt,int tar,int val){
if(!rt)rt=++cnt;
if(l==r){mx[rt]=max(mx[rt],val);return rt;}
int mid=(l+r)>>1;
if(tar<=mid)ls[rt]=ins(l,mid,ls[rt],tar,val);
else rs[rt]=ins(mid+1,r,rs[rt],tar,val);
push_up(rt);
return rt;
}
int query(int l,int r,int rt,int tl,int tr){
if(!rt)return 0;
if(tl<=l&&r<=tr)return mx[rt];
int ans=0;
int mid=(l+r)>>1;
if(tl<=mid)ans=max(ans,query(l,mid,ls[rt],tl,tr));
if(tr>=mid+1)ans=max(ans,query(mid+1,r,rs[rt],tl,tr));
return ans;
}
}ta,tb;
int a[maxn],b[maxn];
vi A,B;
int debug=0;
int main(){
ios::sync_with_stdio(0);
int n;cin>>n;
rep(i,1,n)cin>>a[i];
rep(i,1,n)cin>>b[i];
ll ans=0;
rep(i,1,n){
ans+=abs(a[i]-b[i]);
if(a[i]<b[i])ta.ins(1,inf,1,min(a[i],b[i]),max(a[i],b[i])),A.pb(i);
else tb.ins(1,inf,1,min(a[i],b[i]),max(a[i],b[i])),B.pb(i);
}
ll st=ans;
rep(i,0,(int)(A.size())-1){
int idx=A[i],l=min(a[idx],b[idx]),r=max(a[idx],b[idx]);
if(debug)cout<<"A rmx="<<min(tb.query(1,inf,1,1,l),r)<<endl;
if(debug)cout<<"(l,r)="<<l<<' '<<r<<endl;
if(debug)cout<<"ans="<<ans<<endl;
ll tmp=min(tb.query(1,inf,1,1,l),r)-l;
ans=min(ans,st-2ll*tmp);
}
rep(i,0,(int)(B.size())-1){
int idx=B[i],l=min(a[idx],b[idx]),r=max(a[idx],b[idx]);
if(debug)cout<<"B rmx="<<min(ta.query(1,inf,1,1,l),r)<<endl;
if(debug)cout<<"(l,r)="<<l<<' '<<r<<endl;
if(debug)cout<<"ans="<<ans<<endl;
ll tmp=min(ta.query(1,inf,1,1,l),r)-l;
ans=min(ans,st-2ll*tmp);
}
cout<<ans<<endl;
return 0;
}