记录编号 | 140961 | 评测结果 | AAAAAAAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [国家集训队2012]世博会 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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; }