记录编号	140961	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]世博会	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	5.315 s
提交时间	2014-11-27 09:56:45	内存使用	91.46 MiB

#include <cstdio>
#include <algorithm>
using namespace std;

int n,m,cnt,a[100010],b[100010],x[100010],y[100010];
long long c[400010],ans;

struct segtr{segtr *l,*r; int v; long long s;}T[4500000];

struct chairmanTree
{
    segtr *tr[100010];
    void init() {for (int i=0;i<=n;++i) tr[i]=&T[0];}
    void insert(segtr* &p,int l,int r,int k)
    {
        T[++cnt]=*p; p=&T[cnt];
        ++p->v; p->s+=c[k];
        int mid=(l+r)>>1; if (l>=r) return;
        if (k<=mid) insert(p->l,l,mid,k);
        else insert(p->r,mid+1,r,k);
    }
    int query(int l,int r,int k)
    {
        segtr *A=tr[l-1],*B=tr[r]; int mid;
        l=1; r=m;
        while (l<r)
        {
            mid=(l+r)>>1;
            if (k<=(B->l->v)-(A->l->v))
            {A=A->l; B=B->l; r=mid;}
            else
            {
                k-=(B->l->v)-(A->l->v);
                A=A->r; B=B->r; l=mid+1;
            }
        }
        return l;
    }
    void stat(int l,int r,int v,bool f,long long &sum,long long &num)
    {
        segtr *A=tr[l-1],*B=tr[r];
        int mid; sum=num=0; l=1; r=m;
        while (l<r)
        {
            mid=(l+r)>>1;
            if (v<=mid)
            {
                if (f)
                {
                    sum+=(B->r->s)-(A->r->s);
                    num+=(B->r->v)-(A->r->v);
                }
                A=A->l; B=B->l; r=mid;
            }
            else
            {
                if (!f)
                {
                    sum+=(B->l->s)-(A->l->s);
                    num+=(B->l->v)-(A->l->v);
                }
                A=A->r; B=B->r; l=mid+1;
            }
        }
        sum+=(B->s)-(A->s); num+=(B->v)-(A->v);
    }
    long long solve(int l,int r)
    {
        int mid=(r-l)>>1,mm=query(l,r,mid+1);
        long long ls,rs,ln,rn;
        stat(l,r,mm,0,ls,ln); stat(l,r,mm,1,rs,rn);
        return rs-ls+(ln-rn)*c[mm];
    }
}TX,TY;

char ch; bool flag;
void read(int& x)
{
    x=0; ch=getchar(); flag=0;
    while (ch<=32) ch=getchar();
    if (ch=='-') {flag=1; ch=getchar();}
    while (ch>32) {x=x*10+ch-48; ch=getchar();}
    if (flag) x=-x;
}

int main()
{
    freopen("nt2012_lhx_dis.in","r",stdin);
    freopen("nt2012_lhx_dis.out","w",stdout);
    int q,i;
    for (i=0;i<4500000;++i) T[i].l=T[i].r=&T[0];
    read(n); read(q); TX.init(); TY.init();
    for (i=1;i<=n;++i) read(a[i]);
    for (i=1;i<=n;++i) read(b[i]);
    for (i=1;i<=n;++i)
    {
        x[i]=a[i]+b[i]; c[++m]=x[i];
        y[i]=a[i]-b[i]; c[++m]=y[i];
    }
    sort(c+1,c+m+1); m=unique(c+1,c+m+1)-c-1;
    for (i=1;i<=n;++i)
    {
        x[i]=lower_bound(c+1,c+m+1,x[i])-c;
        y[i]=lower_bound(c+1,c+m+1,y[i])-c;
        TX.tr[i]=TX.tr[i-1]; TX.insert(TX.tr[i],1,m,x[i]);
        TY.tr[i]=TY.tr[i-1]; TY.insert(TY.tr[i],1,m,y[i]);
    }
    while (q--)
    {
        int l,r; read(l); read(r);
        ans=TX.solve(l,r)+TY.solve(l,r);
        printf("%lld",ans>>1);
        if (ans&1) printf(".50\n");
        else printf(".00\n");
    }
    fclose(stdin); fclose(stdout);
    return 0;
}