Description
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。
我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。
Input
第一行包含一个正整数n，表示敌军导弹数量；
下面 行按顺序给出了敌军所有导弹信息：
第i+1行包含2个正整数hi和vi，分别表示第 枚导弹的高度和速度。
Output
输出包含两行。
第一行为一个正整数，表示最多能拦截掉的导弹数量；
第二行包含n个0到1之间的实数，第i个数字表示第i枚导弹被拦截掉的概率（你可以保留任意多位有效数字）。
Sample Input
3 30
4 40
6 60
3 30
Sample Output
0.33333 0.33333 0.33333 1.00000
【数据规模和约定】
对于100%的数据，1≤n≤5*104， 1≤hi ，vi≤109；
均匀分布着约30%的数据，所有vi均相等。
均匀分布着约50%的数据，满足1≤hi ，vi≤1000。
HINT
鸣谢kac提供sj程序！
Source
第一轮day2
~~~~~~~~~~~~~~~~~~~~~~~~
CDQ分治+树状数组~
这道题看起来很麻烦，实际上也确实很麻烦……是我写过的最高端的CDQ分治了~
先离散化h和v，然后把序列翻转方便求LIS，CDQ分治一遍求出来f[i][0]和g[i][0]分别表示到i结束且包含i的最长上升子序列长度，以及这个长度所包含的情况数。
然后再翻转序列，求一遍f[i][1]和g[i][1]，即从i开始的最长上升子序列，最后用f[i][0]+f[i][1]-1更新答案即可。
注意：
1.不能用ans[a[i].id]的方式更新答案……我不知道是为什么……反正这样写第一个答案不对……
2.如果中间我开double的地方写成了int，最后才强制转化的话是WA的；
3.最后要判断一下0.00000的情况；
4.我在写树状数组的时候少判了else if(now.w==c[u].w)这一句，样例测不出来。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;int n,tot,tot1,tot2,q[50001],kk1[50001],kk2[50001],ans;
double num;map<int,int> id1,id2;struct node{int h,v,id,f[2];double g[2];
}a[50001],b[50001];struct bit{int w;double num;
}c[50001];bool operator < (node u,node v)
{return u.h==v.h ? u.id<v.id:u.h<v.h;
}bool cmp(node u,node v)
{return u.id<v.id;
}int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int w,double k)
{for(;u<=tot1;u+=u&(-u))if(c[u].w<w){if(!c[u].w) q[++tot]=u;c[u].w=w;c[u].num=k;}else if(c[u].w==w) c[u].num+=k;
}bit cal(int u)
{bit now;now.w=now.num=0;for(;u;u-=u&(-u))if(c[u].w>now.w) now=c[u];else if(now.w==c[u].w) now.num+=c[u].num;return now;
}void sol(int l,int r,int flag)
{if(l==r){if(a[l].f[flag]<1) a[l].f[flag]=a[l].g[flag]=1;return;}int mid=l+r>>1,l1=l,l2=mid+1;for(int i=l;i<=r;i++)if(a[i].id<=mid) b[l1++]=a[i];else b[l2++]=a[i];for(int i=l;i<=r;i++) a[i]=b[i];sol(l,mid,flag);sort(a+l,a+mid+1);l1=l;for(int i=mid+1;i<=r;i++){while(l1<=mid && a[i].h>=a[l1].h) add(a[l1].v,a[l1].f[flag],a[l1].g[flag]),l1++;bit now=cal(a[i].v);if(!now.w) continue;if(now.w+1>a[i].f[flag]) a[i].f[flag]=now.w+1,a[i].g[flag]=now.num;else if(now.w+1==a[i].f[flag]) a[i].g[flag]+=now.num;}for(int i=1;i<=tot;i++) c[q[i]].w=c[q[i]].num=0;tot=0;sol(mid+1,r,flag);
}int main()
{n=read();for(int i=1;i<=n;i++) kk2[i]=a[i].h=read(),kk1[i]=a[i].v=read(),a[i].id=i;sort(kk1+1,kk1+n+1);tot1=unique(kk1+1,kk1+n+1)-kk1-1;for(int i=1;i<=tot1;i++) id1[kk1[i]]=i;for(int i=1;i<=n;i++) a[i].v=tot1-id1[a[i].v]+1;sort(kk2+1,kk2+n+1);tot2=unique(kk2+1,kk2+n+1)-kk2-1;for(int i=1;i<=tot2;i++) id2[kk2[i]]=i;for(int i=1;i<=n;i++) a[i].h=tot2-id2[a[i].h]+1;sort(a+1,a+n+1);sol(1,n,0);for(int i=1;i<=n;i++) a[i].id=n-a[i].id+1,a[i].h=tot2-a[i].h+1,a[i].v=tot1-a[i].v+1;reverse(a+1,a+n+1);sort(a+1,a+n+1);sol(1,n,1);sort(a+1,a+n+1,cmp);reverse(a+1,a+n+1);for(int i=1;i<=n;i++)if(a[i].f[0]>ans) ans=a[i].f[0],num=a[i].g[0];else if(a[i].f[0]==ans) num+=a[i].g[0];printf("%d\n",ans);for(int i=1;i<=n;i++)if(a[i].f[0]+a[i].f[1]-1<ans) printf("0.00000 ");else printf("%.5lf ",a[i].g[0]*a[i].g[1]/num);return 0;
}