[xsy1144]选物品

题意：给定$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<stdio.h>
#include<algorithm>
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);
	}
}

巴特西

[xsy1144]选物品

最新文章

热门文章