记录编号	371967	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]世博会	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	5.351 s
提交时间	2017-02-17 14:17:01	内存使用	77.83 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
double X[maxn],Y[maxn],stx[maxn],sty[maxn],sx[maxn],sy[maxn];
int n,Q,rx[maxn],ry[maxn],Nx,Ny;
struct Rabit_q{int cnt;double sum;};
struct Rabit_Trie{
    int RT,cnt,size[maxn*20],ch[maxn*20][2],N;double sum[maxn*20];
    Rabit_Trie(){rx[0]=ry[0]=RT=cnt=1,N=17;}
    inline int set(int r0,int key,double v){
        int x=++cnt,res=x;bool b;
        size[x]++,sum[x]+=v;
        for(int i=N;~i;i--){
            b=key>>i&1;
            ch[x][!b]=ch[r0][!b],ch[x][b]=++cnt;
            x=ch[x][b],r0=ch[r0][b],size[x]=size[r0]+1,sum[x]=sum[r0]+v;
        }
        return res;
    }
    inline Rabit_q Sum(int r0,int rt,int key){
        key++;Rabit_q res;res.cnt=0,res.sum=0;
        for(int i=N;~i;i--){
            if(key>>i&1)res.sum+=sum[ch[rt][0]]-sum[ch[r0][0]],
                res.cnt+=size[ch[rt][0]]-size[ch[r0][0]],
                rt=ch[rt][1],r0=ch[r0][1];
            else rt=ch[rt][0],r0=ch[r0][0];
        }
        return res;
    }
    inline int get(int r0,int rt,int th){
        int res=0,tmp;
        for(int i=N;~i;i--){
            tmp=size[ch[rt][0]]-size[ch[r0][0]];
            if(th>tmp)th-=tmp,rt=ch[rt][1],r0=ch[r0][1],res|=1<<i;
            else rt=ch[rt][0],r0=ch[r0][0];
        }
        return res;
    }
}Tx,Ty;
inline void Rabit_in(){
    scanf("%d%d",&n,&Q);int i,A,B;double tx,ty;
    for(i=1;i<=n;i++)scanf("%lf",&X[i]);
    for(i=1;i<=n;i++)scanf("%lf",&Y[i]);
    for(i=1;i<=n;i++)
        tx=X[i]+Y[i],ty=X[i]-Y[i],
        stx[i]=X[i]=tx*0.5,sty[i]=Y[i]=ty*0.5,
        sx[i]=X[i]+sx[i-1],sy[i]=Y[i]+sy[i-1];
    sort(stx+1,stx+n+1),sort(sty,sty+n+1);
    Nx=unique(stx+1,stx+n+1)-stx-1,Ny=unique(sty+1,sty+n+1)-sty-1;
    for(i=1;i<=n;i++)
        A=lower_bound(stx+1,stx+Nx+1,X[i])-stx,
        B=lower_bound(sty+1,sty+Ny+1,Y[i])-sty,
        rx[i]=Tx.set(rx[i-1],A,X[i]),ry[i]=Ty.set(ry[i-1],B,Y[i]);
}
inline void Rabit_ans(){
    int s,t,mid,x,y;Rabit_q tx,ty;
    while(Q--)
        scanf("%d%d",&s,&t),mid=(t-s+1+1)/2,//ceil
        x=Tx.get(rx[s-1],rx[t],mid),y=Ty.get(ry[s-1],ry[t],mid),
        tx=Tx.Sum(rx[s-1],rx[t],x),ty=Ty.Sum(ry[s-1],ry[t],y),
        printf("%.2f\n",
        (sx[t]-sx[s-1]-tx.sum)-stx[x]*(t-s+1-tx.cnt)+stx[x]*tx.cnt-tx.sum+
        (sy[t]-sy[s-1]-ty.sum)-sty[y]*(t-s+1-ty.cnt)+sty[y]*ty.cnt-ty.sum);
}
int main(){
    freopen("nt2012_lhx_dis.in","r",stdin);freopen("nt2012_lhx_dis.out","w",stdout);
    Rabit_in();Rabit_ans();
}