首页 > 代码库 > BZOJ 2244 [SDOI2011]拦截导弹 ——CDQ分治
BZOJ 2244 [SDOI2011]拦截导弹 ——CDQ分治
三维偏序,直接CDQ硬上。
正反两次CDQ统计结尾的方案数,最后统计即可。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=i;--i) #define ll long double #define maxn 50005 struct Mis{ int id,h,v; void print() { printf("The ID %d High %d Speed %d\n",id,h,v); } }a[maxn]; int f[maxn][2],n,h[maxn],v[maxn],htop,vtop; ll g[maxn][2]; bool cmp1(Mis a,Mis b){return a.id<b.id;} bool cmp2(Mis a,Mis b){return a.h<b.h;} int mx[maxn]; ll cnt[maxn]; void add(int x,int f,ll g) { for (;x<maxn;x+=x&(-x)) if (mx[x]==f) cnt[x]+=g; else if (mx[x]<f) mx[x]=f,cnt[x]=g; else break; } int qmx(int x) { int ret=0; for (;x;x-=x&(-x)) ret=max(ret,mx[x]); return ret; } ll qcnt(int x,int m) { ll ret=0; for (;x;x-=x&(-x)) if (mx[x]==m) ret+=cnt[x]; return ret; } void del(int x) { for (;x<maxn;x+=x&(-x)) cnt[x]=mx[x]=0; } void CDQ(int l,int r,int flag) { if (l==r) { if (f[a[l].id][flag]<1) { g[a[l].id][flag]=f[a[l].id][flag]=1; } return ; } int mid=l+r>>1; sort(a+l,a+r+1,cmp1); CDQ(l,mid,flag); sort(a+l,a+mid+1,cmp2); sort(a+mid+1,a+r+1,cmp2); int pl=l; F(i,mid+1,r) { while (a[pl].h<=a[i].h&&pl<=mid) add(a[pl].v,f[a[pl].id][flag],g[a[pl].id][flag]),pl++; int tmp=qmx(a[i].v)+1; if (tmp==1) continue; if (tmp>f[a[i].id][flag]) { f[a[i].id][flag]=tmp; g[a[i].id][flag]=qcnt(a[i].v,tmp-1); } else if (tmp==f[a[i].id][flag]) g[a[i].id][flag]+=qcnt(a[i].v,tmp-1); } F(i,l,pl-1) del(a[i].v); CDQ(mid+1,r,flag); } void print() { int ans=0; F(i,1,n) ans=max(ans,f[i][0]); printf("%d\n",ans); ll sum=0; F(i,1,n) if (f[i][0]==ans) sum+=g[i][0]*g[n-i+1][1]; F(i,1,n) { if (f[i][0]+f[n-i+1][1]-1==ans) printf("%.5Lf ",g[i][0]*g[n-i+1][1]/sum); else printf("0 "); } } int main() { scanf("%d",&n);htop=vtop=n; F(i,1,n) { scanf("%d%d",&a[i].h,&a[i].v); a[i].id=i;h[i]=a[i].h;v[i]=a[i].v; } sort(h+1,h+htop+1); sort(v+1,v+vtop+1); htop=unique(h+1,h+htop+1)-h-1; vtop=unique(v+1,v+vtop+1)-v-1; F(i,1,n) { a[i].h=lower_bound(h+1,h+htop+1,a[i].h)-h; a[i].v=lower_bound(v+1,v+vtop+1,a[i].v)-v; } F(i,1,n) { a[i].h=htop-a[i].h+1; a[i].v=vtop-a[i].v+1; } CDQ(1,n,0); F(i,1,n) { a[i].id=n-a[i].id+1; a[i].v=vtop-a[i].v+1; a[i].h=htop-a[i].h+1; } CDQ(1,n,1); print(); }
BZOJ 2244 [SDOI2011]拦截导弹 ——CDQ分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。