CF1513F Swapping Problem

首先我们观察到有一个性质：如果我们把$a_i<b_i$的位置放入$A$集合，$a_i>b_i$的位置放入$B$集合，那么最后一定是选择一个$A$集合元素和一个$B$集合元素进行交换最优秀。

然后我就一直在想，把每个位置转化成二维平面的一个点，然后跑平面最近哈夫曼距离啥的。硬是没想到一个关键的性质：如果把每个位置的$a,b$都组成一个线段，交换两个位置减少的代价就是线段的交乘二。所以现在问题就转化为了：两个集合分别有一堆线段，然后从两个集合各自拿出一条线段求交，要求交的值最大。

那我们分类讨论，先假设$A$中线段的$l$比较小，那么就对$A$中所有元素建一个下标为$l$，权值为$r$的线段树，然后对于$B$中的每个线段丢进去查找满足条件$l_A\leq l_B$中，$r_A$的最大值。这样就能计算出交的大小了，另一种同理。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#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;
}