[SDOI2011]拦截导弹

肝了半个下午+半个晚上

传送门

提供一篇k-d tree题解。

首先第一问就是裸的三维偏序，还给你排好序消去了一维。

那么在k-d tree中加一个横纵坐标都是无限大的点做起点，这个点的答案是0，方案数是1（后面反着做的时候要加一个横纵坐标都是无限小的点）。之后用k-d tree模拟就好了。注意要在k-d tree中维护当前矩形的答案和方案数、当前点的答案和方案数。我的写法是先把所有点去重后都加进k-d tree里，所以要维护每个点是否被激活，这种做法比插入节点定期重构快。

之后每个点被选中的概率=经过它的方案数/总方案数。

而经过它的方案数=从前面经过它的方案数*从后面经过它的方案数。

这里说的从前面和从后面就是正着dp和倒着dp的意思，反正很简单大家都明白。

而一个点能被经过首先需要从前面经过它的答案+从后面经过它的答案-1=整个序列的答案。

反正就是把暴力的dp加一个数据结构优化一下就好了。

但是不是太好写。。我为了只写一遍k-d tree费尽了心思。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(int&x){scanf("%d",&x);}
#endif
struct point{int d[2],h;}a[50010],b[50010],c[50010];
struct mis{int u; double v;}dp[50010][2],ans;
struct kdtree{
    int d[2],x[2],y[2],ch[2],sz,lv,u,u1;
    double v,v1;
}t[50010];
int root,tot,n,u,f,p,res,m;
double sum,pos[50010];
inline bool cmp(point x,point y){return x.d[u]<y.d[u];}
inline bool cmp2(point x,point y){
    return (x.d[0]<y.d[0])||(x.d[0]==y.d[0]&&x.d[1]<y.d[1]);
}
inline void pushup(int rt){
    int l=t[rt].ch[0],r=t[rt].ch[1];
    if (l){
        t[rt].x[0]=min(t[rt].x[0],t[l].x[0]);
        t[rt].y[0]=min(t[rt].y[0],t[l].y[0]);
        t[rt].x[1]=max(t[rt].x[1],t[l].x[1]);
        t[rt].y[1]=max(t[rt].y[1],t[l].y[1]);
    }
    if (r){
        t[rt].x[0]=min(t[rt].x[0],t[r].x[0]);
        t[rt].y[0]=min(t[rt].y[0],t[r].y[0]);
        t[rt].x[1]=max(t[rt].x[1],t[r].x[1]);
        t[rt].y[1]=max(t[rt].y[1],t[r].y[1]);
    }
}
inline int build(int d,int l,int r){
    if (l>r) return 0; u=d;
    int mid=(l+r)>>1,rt=++tot;
    nth_element(c+l,c+mid,c+r+1,cmp);
    t[rt].x[0]=t[rt].x[1]=t[rt].d[0]=c[mid].d[0];
    t[rt].y[0]=t[rt].y[1]=t[rt].d[1]=c[mid].d[1];
    t[rt].ch[0]=build(d^1,l,mid-1);
    t[rt].ch[1]=build(d^1,mid+1,r);
    pushup(rt); return rt;
}
inline void up(int rt){
    int l=t[rt].ch[0],r=t[rt].ch[1];
    t[rt].sz=t[l].sz+t[r].sz+t[rt].lv;
    int x=max(t[l].u,t[r].u); double y=0;
    y+=t[l].v*(x==t[l].u)+t[r].v*(x==t[r].u);
    if (t[rt].u1>x) t[rt].v=t[rt].v1;
    if (t[rt].u1==x) t[rt].v=y+t[rt].v1;
    if (t[rt].u1<x) t[rt].u=x,t[rt].v=y;
}
void ins(int rt,point x){
    if (t[rt].d[0]==x.d[0]&&t[rt].d[1]==x.d[1]){
        t[rt].lv++; t[rt].sz++;
        if (t[rt].u1<dp[x.h][f].u)
            t[rt].u1=dp[x.h][f].u,t[rt].v1=dp[x.h][f].v;
        else
            if (t[rt].u1==dp[x.h][f].u) t[rt].v1+=dp[x.h][f].v;
        if (t[rt].u<dp[x.h][f].u)
            t[rt].u=dp[x.h][f].u,t[rt].v=dp[x.h][f].v;
        else
            if (t[rt].u==dp[x.h][f].u) t[rt].v+=dp[x.h][f].v;
        return;
    }
    int l=t[rt].ch[0],r=t[rt].ch[1];
    if (t[l].x[0]<=x.d[0]&&x.d[0]<=t[l].x[1]&&
        t[l].y[0]<=x.d[1]&&x.d[1]<=t[l].y[1])
        ins(l,x);
    if (t[r].x[0]<=x.d[0]&&x.d[0]<=t[r].x[1]&&
        t[r].y[0]<=x.d[1]&&x.d[1]<=t[r].y[1])
        ins(r,x);
    up(rt); return;
}
void query(int rt,point x){
    if (!rt||!t[rt].sz) return;
    if (t[rt].x[f^1]*p<x.d[0]*p||t[rt].y[f^1]*p<x.d[1]*p)
        return;
    if (t[rt].x[f]*p>=x.d[0]*p&&t[rt].y[f]*p>=x.d[1]*p){
        if (t[rt].u==ans.u) ans.v+=t[rt].v;
        if (t[rt].u>ans.u) ans.u=t[rt].u,ans.v=t[rt].v;
        return;
    }
    if (t[rt].d[0]*p>=x.d[0]*p&&t[rt].d[1]*p>=x.d[1]*p&&t[rt].lv){
        if (t[rt].u1==ans.u) ans.v+=t[rt].v1;
        if (t[rt].u1>ans.u) ans.u=t[rt].u1,ans.v=t[rt].v1;
    }
    int l=t[rt].ch[0],r=t[rt].ch[1];
    if (t[l].u>t[r].u){
        if (t[l].u>=ans.u) query(l,x);
        if (t[r].u>=ans.u) query(r,x);
    }
    else{
        if (t[r].u>=ans.u) query(r,x);
        if (t[l].u>=ans.u) query(l,x);
    }
}
int main(){
    read(n);
    for (int i=1; i<=n; i++){
        read(a[i].d[0]),read(a[i].d[1]);
        a[0].d[0]=max(a[0].d[0],a[i].d[0]);
        a[0].d[1]=max(a[0].d[1],a[i].d[1]);
        b[i]=a[i]; b[i].h=i;
    }
    a[n+1].d[0]=0,a[n+1].d[1]=0;
    b[0]=a[0]; b[n+1]=a[n+1]; b[n+1].h=n+1;
    sort(a,a+n+2,cmp2); c[++m]=a[0];
    for (int i=1; i<=n+1; i++)
        if (a[i].d[0]!=a[i-1].d[0]||a[i].d[1]!=a[i-1].d[1])
            c[++m]=a[i];
    root=build(0,1,m);
    p=1; f=0; dp[0][0]=(mis){0,1};
    ins(root,b[0]);
    for (int i=1; i<=n; i++){
        query(root,b[i]); ans.u++;
        dp[i][f]=ans; ins(root,b[i]);
        res=max(res,ans.u); ans=(mis){0,0};
    }
    printf("%d\n",res);
    for (int i=1; i<=n; i++)
        if (dp[i][0].u==res) sum+=dp[i][0].v;
    for (int i=1; i<=tot; i++)
        t[i].lv=t[i].sz=t[i].u1=t[i].u=t[i].v1=t[i].v=0;
    f=1; p=-1; dp[n+1][1]=(mis){0,1};
    ins(root,b[n+1]);
    for (int i=n; i>=1; i--){
        query(root,b[i]); ans.u++;
        dp[i][f]=ans; ins(root,b[i]);
        ans=(mis){0,0};
    }
    for (int i=1; i<=n; i++){
        if (dp[i][0].u+dp[i][1].u-1==res)
            pos[i]=(dp[i][0].v*dp[i][1].v)/sum;
        printf("%.5lf ",pos[i]);
    }
    return 0;
}