Description
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。
我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。
Input
第一行包含一个正整数n，表示敌军导弹数量；
下面 行按顺序给出了敌军所有导弹信息：
第i+1行包含2个正整数h和v，分别表示第 枚导弹的高度和速度。
Output
输出包含两行。
第一行为一个正整数，表示最多能拦截掉的导弹数量；
第二行包含n个0到1之间的实数，第i个数字表示第i枚导弹被拦截掉的概率（你可以保留任意多位有效数字）。
Sample Input
4
3 30
4 40
6 60
3 30
3 30
4 40
6 60
3 30
Sample Output
2
0.33333 0.33333 0.33333 1.00000
0.33333 0.33333 0.33333 1.00000
解题思路：
让我想起了前一阵学弟们做的题（手动滑稽）
这道题第一问相当于一个二维LIS。
主要是第二问，我们只需统计有多少最大的答案，和节点在多少方案中，最后相除即可。
最长的只需枚举统计就好了。
而节点在多少方案中可以统计其最长前缀LIS和最长后缀LIS，如果相加等于答案+1那么就合法。
相当于最长前缀LIS数量*最长后缀LIS数量。
这个可以用结构体重载运算符实现。
最后中间运算变量可能>10中间变量要用double，因为double不会爆而是牺牲精度。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll spc<<1
#define rrr spc<<1|1
const int N=;
const int M=;
struct trnt{
int maxv;
double maxt;
}tr[M],strnt;
struct data{
int t;
int h;
int tv;
int v;
}d[N];
int n;
int tot;
int cnt;
double sum;
trnt f[N],g[N];
bool cmpb(data a,data b){return a.t<b.t;}
bool cmph(data a,data b){return a.h>b.h;}
bool cmpv(data a,data b){return a.tv<b.tv;}
trnt max(trnt x,trnt y)
{
trnt ans;
if(x.maxv<y.maxv)
ans=y;
else if(x.maxv>y.maxv)
ans=x;
else
ans=(trnt){x.maxv,x.maxt+y.maxt};
return ans;
}
void pushup(int spc)
{
tr[spc]=max(tr[lll],tr[rrr]);
return ;
}
void update(int l,int r,int pos,int spc,int v,double t)
{
if(l==r)
{
if(v==-)
tr[spc]=strnt;
else{
if(tr[spc].maxv<v)
tr[spc]=(trnt){v,t};
else if(tr[spc].maxv==v)
tr[spc].maxt+=t;
}
return ;
}
int mid=(l+r)>>;
if(pos<=mid)
update(l,mid,pos,lll,v,t);
else
update(mid+,r,pos,rrr,v,t);
pushup(spc);
return ;
}
trnt query(int ll,int rr,int l,int r,int spc)
{
if(ll>r||l>rr)
return strnt;
if(ll<=l&&r<=rr)
return tr[spc];
int mid=(l+r)>>;
return max(query(ll,rr,l,mid,lll),query(ll,rr,mid+,r,rrr));
}
void CDQ(int l,int r)
{
if(l==r)
return ;
int mid=(l+r)>>;
CDQ(l,mid);
std::sort(d+l,d+mid+,cmph);
std::sort(d+mid+,d+r+,cmph);
int j=l;
for(int i=mid+;i<=r;i++)
{
for(;j<=mid&&d[j].h>=d[i].h;j++)
update(,n,d[j].v,,f[d[j].t].maxv,f[d[j].t].maxt);
trnt tmp=query(d[i].v,n,,n,);
tmp.maxv++;
f[d[i].t]=max(f[d[i].t],tmp);
}
for(int i=l;i<j;i++)
update(,n,d[i].v,,-,);
std::sort(d+mid+,d+r+,cmpb);
CDQ(mid+,r);
return ;
}
void Dark_CDQ(int l,int r)
{
if(l==r)
return ;
int mid=(l+r)>>;
Dark_CDQ(mid+,r);
std::sort(d+l,d+mid+,cmph);
std::sort(d+mid+,d+r+,cmph);
int j=r;
for(int i=mid;i>=l;i--)
{
for(;j>=mid+&&d[j].h<=d[i].h;j--)
update(,n,d[j].v,,g[d[j].t].maxv,g[d[j].t].maxt);
trnt tmp=query(,d[i].v,,n,);
tmp.maxv++;
g[d[i].t]=max(g[d[i].t],tmp);
}
for(int i=r;i>j;i--)
update(,n,d[i].v,,-,);
std::sort(d+l,d+mid+,cmpb);
Dark_CDQ(l,mid);
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&d[i].h,&d[i].tv);
d[i].t=i;
}
std::sort(d+,d+n+,cmpv);
tot++;
d[].v=;
for(int i=;i<=n;i++)
{
if(d[i].tv!=d[i-].tv)
tot++;
d[i].v=tot;
}
std::sort(d+,d+n+,cmpb);
for(int i=;i<=n;i++)
f[i]=g[i]=(trnt){,};
CDQ(,n);
trnt ans=strnt;
for(int i=;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",ans.maxv);
for(int i=;i<=n;i++)
if(f[i].maxv==ans.maxv)
sum+=(double)(f[i].maxt);
std::sort(d+,d+n+,cmpb);
Dark_CDQ(,n);
std::sort(d+,d+n+,cmpb);
for(int i=;i<=n;i++)
{
if(g[i].maxv+f[i].maxv-==ans.maxv)
printf("%.5lf ",(double)(f[i].maxt)*(double)(g[i].maxt)/sum);
else
printf("0.00000 ");
}
puts("");
return ;
}