题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2665
代码：
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<algorithm> #define fi first #define se second #define INF 0x3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) #define lowbit(x) ((x)&(-x)) using namespace std; const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=1e5+6; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; struct node{ int siz,lc,rc; }a[maxn*20]; int s[maxn]; struct nub{ int st,num; bool operator<(const nub &u)const{ return num<u.num; } }u[maxn]; int tot=0,rt[maxn]; void Build(int d,int l,int r){ a[d].siz=0; if(l==r){ return ; } int m=(l+r)>>1; a[d].lc=tot++;a[d].rc=tot++; Build(a[d].lc,l,m); Build(a[d].rc,m+1,r); } void updata(int st,int d,int last,int l,int r){ a[d].siz=a[last].siz+1; if(l==r){ return ; } int mid=(l+r)>>1; if(st<=mid){ a[d].rc=a[last].rc; a[d].lc=tot++; updata(st,a[d].lc,a[last].lc,l,mid); } else if(st>mid){ a[d].lc=a[last].lc; a[d].rc=tot++; updata(st,a[d].rc,a[last].rc,mid+1,r); } } int query(int k,int last,int now,int l,int r){ if(l==r){ return l; } int mid=(l+r)>>1; if(k<=a[a[now].lc].siz-a[a[last].lc].siz){ return query(k,a[last].lc,a[now].lc,l,mid); } else{ return query(k-(a[a[now].lc].siz-a[a[last].lc].siz),a[last].rc,a[now].rc,mid+1,r); } } int b[maxn]; int main(){ int n,m,t; scanf("%d",&t); while(t--){ tot=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&u[i].num); u[i].st=i; } sort(u+1,u+1+n); int cnt=1; s[cnt]=u[1].num; b[u[1].st]=1; for(int i=2;i<=n;i++){ if(u[i].num!=u[i-1].num){ cnt++; s[cnt]=u[i].num; } b[u[i].st]=cnt; } rt[0]=tot++; Build(rt[0],1,cnt); for(int i=1;i<=n;i++){ rt[i]=tot++; updata(b[i],rt[i],rt[i-1],1,cnt); } int l,r,k; for(int i=1;i<=m;i++){ scanf("%d%d%d",&l,&r,&k); printf("%d ",s[query(k,rt[l-1],rt[r],1,cnt)]); } } system("pause"); return 0; }
HDU1007
http://acm.hdu.edu.cn/showproblem.php?pid=1007
方差优化：
#include<bits/stdc++.h> #define fi first #define se second #define INF 0x3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) #define lowbit(x) ((x)&(-x)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=2e5+8; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; using namespace std; int kdd; struct node{ int id,di; double g[2]; bool operator<(const node &u)const{ return g[kdd]<u.g[kdd]; } }kdt[maxn<<2],data[maxn]; bool flag[maxn<<2]; double dis(node a,node b){ return (a.g[0]-b.g[0])*(a.g[0]-b.g[0])+(a.g[1]-b.g[1])*(a.g[1]-b.g[1]); } double fx(int l,int r,int j){ double as=0.0; for(int i=l;i<=r;i++){ as+=data[i].g[j]; } as/=(double)(r-l+1); double f=0.0; for(int i=l;i<=r;i++){ f+=(data[i].g[j]-as)*(data[i].g[j]-as); } f/=(double)(r-l+1); return f; } void build(int l,int r,int rt){ if(l>r) return ; if(fx(l,r,0)>fx(l,r,1)){ kdd=0; } else{ kdd=1; } flag[rt]=1; int mid=(l+r)>>1; nth_element(data+l,data+mid,data+r+1); kdt[rt]=data[mid]; kdt[rt].di=kdd; flag[rt<<1]=flag[rt<<1|1]=0; if(l<=mid-1){ build(l,mid,rt<<1); } if(mid+1<=r){ build(mid+1,r,rt<<1|1); } } pair<double,node> ans; double mi; void query(int rt,node p){ int kd=kdt[rt].di; pair<double,node> now={dis(p,kdt[rt]),kdt[rt]}; int x=rt<<1; int y=rt<<1|1; if(p.g[kd]>=kdt[rt].g[kd]){ swap(x,y); } if(flag[x]) query(x,p); bool ff=0; if(ans.fi==-1.0){ ff=1; if(p.id!=kdt[rt].id){ ans=now; } } else{ if(p.id!=kdt[rt].id&&(now.fi<ans.fi||now.fi==ans.fi&&now.se.id<ans.se.id)){ ans=now; } if((kdt[rt].g[kd]-p.g[kd])*(kdt[rt].g[kd]-p.g[kd])<ans.fi){ ff=1; } } if(flag[y]&&ff){ query(y,p); } } int main(){ int n; while(~scanf("%d",&n)&&n!=0){ for(int i=1;i<=n;i++){ for(int j=0;j<2;j++){ scanf("%lf",&data[i].g[j]); } data[i].id=i; } build(1,n,1); mi=1000000000.0; for(int i=1;i<=n;i++){ ans.fi=-1.0; query(1,data[i]); mi=min(mi,sqrt(ans.fi)); } mi/=2.0; printf("%.2lf ",mi); } }