记录编号	163771	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]世博会	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	5.164 s
提交时间	2015-05-25 21:33:33	内存使用	97.95 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

#define M 2500010
#define N 100010
#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define LL long long

using namespace std;

inline void file(){
	freopen("nt2012_lhx_dis.in","r",stdin);
	freopen("nt2012_lhx_dis.out","w",stdout);
}

int a0[N<<1],tot0;

struct SEGTREE{
	struct segt{
		int sum;
		LL sumv;
	}tree[M];

	#define sum(x) tree[x].sum
	#define sumv(x) tree[x].sumv

	int ch[M][2],n,tot,root[N];

	int change(int o,int l,int r,int qx){
		int x=++tot;
		l(x)=l(o); r(x)=r(o);
		sumv(x)=sumv(o)+a0[qx];
		sum(x)=sum(o)+1;
		if(l==r) return x;
		int mid=(l+r)>>1;
		if(qx<=mid) l(x)=change(l(o),l,mid,qx);
		else r(x)=change(r(o),mid+1,r,qx);
		return x;
	}
	
	inline void init(int src[],int n){
		tot=0;
		for(int i=1;i<=n;i++)
			root[i]=change(root[i-1],1,tot0,src[i]);
	}
	
	LL sum,sumv;
	
	int ask(int p,int q,int l,int r,int k){
		if(l==r) return l;
		int mid=(l+r)>>1;
		int tmp=sum(l(p))-sum(l(q));
		if(tmp<k) return ask(r(p),r(q),mid+1,r,k-tmp);
		else return ask(l(p),l(q),l,mid,k);
	}
	
	inline int ask(int l,int r,int k){
		return ask(root[r],root[l-1],1,tot0,k);
	}
	
	void ask2(int l,int r,int qv,int t){
		int p=root[r],q=root[l-1];
		sum=0; sumv=0; l=1; r=tot0;
		while(l<r){
			int mid=(l+r)>>1;
			if(qv<=mid){
				if(t) sum+=sum(r(p))-sum(r(q));
				if(t) sumv+=sumv(r(p))-sumv(r(q));
				p=l(p); q=l(q); r=mid;
			}
			else{
				if(!t) sum+=sum(l(p))-sum(l(q));
				if(!t) sumv+=sumv(l(p))-sumv(l(q));
				p=r(p); q=r(q); l=mid+1;
			}
		}
		sum+=sum(p)-sum(q);
		sumv+=sumv(p)-sumv(q);
	}
	
	inline LL com_ask(int l,int r){
		int tmp=ask(l,r,(r-l)/2+1);
		LL L1,R1,L2,R2;
		ask2(l,r,tmp,0); L1=sumv; R1=sum;
		ask2(l,r,tmp,1); L2=sumv; R2=sum;
		return L2-L1+(R1-R2)*(LL)a0[tmp];
	}
}T1,T2;

int n,m,a[N],b[N];

int main(){
	file();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		int t1=a[i]+b[i];
		int t2=a[i]-b[i];
		a[i]=t1; a0[++a0[0]]=t1;
		b[i]=t2; a0[++a0[0]]=t2;
	}
	sort(a0+1,a0+a0[0]+1);
	tot0=1;
	for(int i=2;i<=a0[0];i++) a0[++tot0]=a0[i];
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(a0+1,a0+tot0+1,a[i])-a0;
		b[i]=lower_bound(a0+1,a0+tot0+1,b[i])-a0;
	}
	T1.init(a,n);
	T2.init(b,n);
	LL ans=0;
	for(int i=1,l,r;i<=m;i++,ans=0){
		scanf("%d%d",&l,&r);
		ans+=T1.com_ask(l,r);
		ans+=T2.com_ask(l,r);
		printf("%.2lf\n",ans/2.0);
	}
	return 0;
}