这像是一个dp
事实上它是一个三维偏序问题
三个维度分别为高度、编号、速度
和陌上花开类似
第一维排序搞定，第二维用CDQ分治，第三维用树状数组维护
定义$f[0/1][i]$分别为以$i$为开头/结尾的LIS长度
$g[0/1][i]$为以$i$为开头/结尾的LIS方案数
树状数组维护这两个值即可
在统计以$i$为结尾时，可以将序列反转，就只需一个CDQ函数就好了
最后统计答案时，若$f[0][i]+f[1][i]-1==ans$，则说明这枚导弹在方案中
它被打下的概率即为有它存在的方案数/总方案数
注意：计算过程中$g$数组必须用double类型，防止爆炸
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef double dd;
const int N=5e4+5;
struct node
{
dd g[2];
int h,v,id,f[2];
inline friend bool operator < (node a,node b)
{
return a.h==b.h?a.id<b.id:a.h<b.h;
}
}t[N],d[N];
int n,hy[N],vy[N],cnt1,cnt2,stack[N],top;
struct BIT
{
int w;
dd sum;
BIT(){w=0; sum=0;}
inline void clear(){w=0; sum=0;}
}c[N];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
bool cmp(node a,node b){return a.id<b.id;}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k,dd s)
{
while (x<=cnt2)
{
if (c[x].w<k)
{
if (!c[x].w) stack[++top]=x;
c[x].w=k; c[x].sum=s;
}
else if (c[x].w==k) c[x].sum+=s;
x+=lowbit(x);
}
}
inline BIT query(int x)
{
BIT res;
while (x)
{
if (c[x].w>res.w) res=c[x];
else if (c[x].w==res.w) res.sum+=c[x].sum;
x-=lowbit(x);
}
return res;
}
void CDQ(int l,int r,int k)
{
if (l==r)
{
if (t[l].f[k]<1) t[l].f[k]=t[l].g[k]=1;
return;
}
int mid=(l+r)>>1,p=l,q=mid+1;
for (reg int i=l;i<=r;i++)
if (t[i].id<=mid) d[p++]=t[i];
else d[q++]=t[i];
for (reg int i=l;i<=r;i++) t[i]=d[i];
CDQ(l,mid,k); p=l; sort(t+l,t+mid+1);
for (reg int i=mid+1;i<=r;i++)
{
while (p<=mid&&t[i].h>=t[p].h) add(t[p].v,t[p].f[k],t[p].g[k]),++p;
BIT res=query(t[i].v); if (!res.w) continue;
if (t[i].f[k]<res.w+1) t[i].f[k]=res.w+1,t[i].g[k]=res.sum;
else if (t[i].f[k]==res.w+1) t[i].g[k]+=res.sum;
}
for (reg int i=1;i<=top;i++) c[stack[i]].clear(); top=0;
CDQ(mid+1,r,k);
}
int main()
{
n=read();
for (reg int i=1;i<=n;i++)
{
t[i].h=read(),t[i].v=read(),t[i].id=i;
hy[i]=t[i].h; vy[i]=t[i].v;
}
sort(hy+1,hy+n+1); sort(vy+1,vy+n+1);
cnt1=unique(hy+1,hy+n+1)-hy-1;
cnt2=unique(vy+1,vy+n+1)-vy-1;
for (reg int i=1;i<=n;i++) t[i].h=cnt1-(lower_bound(hy+1,hy+cnt1+1,t[i].h)-hy)+1;
for (reg int i=1;i<=n;i++) t[i].v=cnt2-(lower_bound(vy+1,vy+cnt2+1,t[i].v)-vy)+1;
sort(t+1,t+n+1); CDQ(1,n,0);
for (reg int i=1;i<=n;i++)
t[i].h=cnt1-t[i].h+1,t[i].v=cnt2-t[i].v+1,t[i].id=n-t[i].id+1;
reverse(t+1,t+n+1); sort(t+1,t+n+1); CDQ(1,n,1);
sort(t+1,t+n+1,cmp); reverse(t+1,t+n+1);
int ans=0; dd sum=0;
for (reg int i=1;i<=n;i++)
if (ans<t[i].f[0]) ans=t[i].f[0],sum=t[i].g[0];
else if (ans==t[i].f[0]) sum+=t[i].g[0];
printf("%d\n",ans);
for (reg int i=1;i<=n;i++)
{
int len=t[i].f[0]+t[i].f[1]-1;
if (len==ans) printf("%.6lf ",t[i].g[0]*t[i].g[1]/sum);
else printf("0.000000 ");
}
return 0;
}
```