$|x_1-x_2|+|y_1-y_2|=\max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|)$

将坐标$(x,y)$逆变换为$(\frac{x+y}{2},\frac{x-y}{2})$后，询问[l,r]的最优解为中位数

离散化后用主席树支持查询

 

#include
     
      #include
      
       typedef long long ll;const int N=100010,M=1800000;int n,q,i,j,x,y,k,X[N],Y[N],lix[N],liy[N];struct ChairTree{int tot,l[M],r[M],v[M],root[N];ll sum[M];int ins(int x,int a,int b,int c,int d){  int y=++tot;v[y]=v[x]+1,sum[y]=sum[x]+d;  if(a==b)return y;  int mid=(a+b)>>1;  if(c<=mid)l[y]=ins(l[x],a,mid,c,d),r[y]=r[x];else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,d);  return y;}inline ll ask(int x,int y,int k){  int a=1,b=n,mid,t,cnt=0;ll ans=0;  while(a
       
        >1,t=v[l[x]]-v[l[y]];    if(k<=t){      cnt+=v[r[x]]-v[r[y]],ans+=sum[r[x]]-sum[r[y]];      x=l[x],y=l[y],b=mid;    }else{      cnt-=t,ans-=sum[l[x]]-sum[l[y]];      k-=t,x=r[x],y=r[y],a=mid+1;    }  }  return ans-sum[x]/v[x]*cnt;}}Tx,Ty;inline int lowerx(int x){  int l=1,r=n,t,mid;  while(l<=r)if(lix[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}inline int lowery(int x){  int l=1,r=n,t,mid;  while(l<=r)if(liy[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}int main(){  scanf("%d%d",&n,&q);  for(i=1;i<=n;i++)scanf("%d",&X[i]);  for(i=1;i<=n;i++)scanf("%d",&j),Y[i]=X[i]-j,X[i]+=j;  for(i=1;i<=n;i++)lix[i]=X[i],liy[i]=Y[i];  std::sort(lix+1,lix+n+1),std::sort(liy+1,liy+n+1);  for(i=1;i<=n;i++)X[i]=lowerx(X[i]),Y[i]=lowery(Y[i]);  for(i=1;i<=n;i++)Tx.root[i]=Tx.ins(Tx.root[i-1],1,n,X[i],lix[X[i]]),Ty.root[i]=Ty.ins(Ty.root[i-1],1,n,Y[i],liy[Y[i]]);  while(q--){    scanf("%d%d",&x,&y),k=(y-x+2)/2;    printf("%.2f\n",(double)(Tx.ask(Tx.root[y],Tx.root[x-1],k)+Ty.ask(Ty.root[y],Ty.root[x-1],k))/2.0);  }  return 0;}