题意：给定$a_{1\cdots n},b_{1\cdots n}$，询问是给定$l,r$，找出$a',b'$使得$\sum\limits_{i=l}^r\max(\left|a'-a_i\right|,\left|b'-b_i\right|)$最小

很妙的转化...

$\max(\left|a_1-a_2\right|,\left|b_1-b_2\right|)=\max(a_1-a_2,a_2-a_1,b_1-b_2,b_2-b_1)$

令$x_1=\frac{a_1+b_1}2,y_1=\frac{a_1-b_1}2$，类似定义$x_2,y_2$，原式变为

$\begin{aligned}\max(x_1+y_1-x_2-y_2,x_2+y_2-x_1-y_1,x_1-y_1-x_2+y_2,x_2-y_2-x_1+y_1)&=\max(x_1-x_2,x_2-x_1)+\max(y_1-y_2,y_2-y_1)\\&=\left|x_1-x_2\right|+\left|y_1-y_2\right|\end{aligned}$

我们现在要找到$x',y'$使得$\sum\limits_{i=l}^r\left|x'-x_i\right|+\left|y'-y_i\right|$最小，拆开之后就变成两个区间中位数，此时可以用可持久化线段树解决

#include
     
      #include
      
       using namespace std;typedef long long ll;struct seg{	int l,r,c;	ll s;}t[4000010];int r1[100010],r2[100010],v[200010],M,N;void modify(int pr,int&nr,int p,int v,int l,int r){	nr=++M;	t[nr]=t[pr];	t[nr].s+=v;	t[nr].c++;	if(l==r)return;	int mid=(l+r)>>1;	if(p<=mid)		modify(t[pr].l,t[nr].l,p,v,l,mid);	else		modify(t[pr].r,t[nr].r,p,v,mid+1,r);}ll d,res;void query(int pr,int nr,int k,int l,int r){	if(l==r){		d=v[l];		return;	}	int mid=(l+r)>>1,lc,rc;	ll ls,rs;	lc=t[t[nr].l].c-t[t[pr].l].c;	rc=t[t[nr].r].c-t[t[pr].r].c;	ls=t[t[nr].l].s-t[t[pr].l].s;	rs=t[t[nr].r].s-t[t[pr].r].s;	if(k<=lc){		query(t[pr].l,t[nr].l,k,l,mid);		res+=rs-rc*d;	}else{		query(t[pr].r,t[nr].r,k-lc,mid+1,r);		res+=d*lc-ls;	}}int a[100010],b[100010];int main(){	int n,m,i,x,y;	scanf("%d%d",&n,&m);	for(i=1;i<=n;i++)scanf("%d",a+i);	for(i=1;i<=n;i++)scanf("%d",b+i);	for(i=1;i<=n;i++){		v[++N]=a[i]+b[i];		v[++N]=a[i]-b[i];	}	sort(v+1,v+N+1);	N=unique(v+1,v+N+1)-v-1;	for(i=1;i<=n;i++){		modify(r1[i-1],r1[i],lower_bound(v+1,v+N+1,a[i]+b[i])-v,a[i]+b[i],1,N);		modify(r2[i-1],r2[i],lower_bound(v+1,v+N+1,a[i]-b[i])-v,a[i]-b[i],1,N);	}	while(m--){		scanf("%d%d",&x,&y);		res=0;		query(r1[x-1],r1[y],(y-x)/2+1,1,N);		query(r2[x-1],r2[y],(y-x)/2+1,1,N);		printf("%lld.%d0\n",res/2,res&1?5:0);	}}