题意：
给定一个序列，每个元素有两个属性 $h$ 和 $v$ ，是导弹的高度和速度，发射的拦截炮弹第一发可以是任意的高度和速度，但是要求每一发炮弹的高度和速度都不能大于前一发。问：
1. 选取最优的发射方案的时候最多能拦截多少发导弹
2. 当有多个拦截导弹数目相同的最优方案的时候，我方会从中随机选取一种方案，现在问在这种策略下，每发炮弹能拦截到导弹的概率是多少
题解：
第一问很明显使用cdq分治加速dp转移算LIS，难点在于第二问。把LIS各个节点的转移看成图上的连边的话，可以得到一个dag，而后可以想见使用dp求出到每个点的在LIS上的路径有多少条，便可以确定随机选取的情况下每个节点被选取到的概率为 经过该点的在LIS上的路径数/所有的在LIS上的路径数 。判断一个点是否在LIS上，我们可以两端各求一次LIS，分别记为 $dpl[i] dpr[i]$ ,则如果当前节点满足 $dpl[i]+dpr[i]=\max\limits_{1\le j\le n} dpl[j]+1$ 则说明其属于某个LIS，+1是为了去除节点本身的重复计算。 为了求出经过某个点的路径数，我们可以用之前 dp求最短路必经边的方法 ，从两端分别跑一次dp，分别记录两端到某个节点的属于LIS的路径数为 $gl[i]\;gr[i]$ ，这样的话经过节点i的路径数就可以表示为 $gl[i]*gr[i]$ ，则每个点被选中的概率就可以被表示为
$$\frac{gl[i]*gr[i}{\sum_{[dpl[k]=LIS]}gl[k]}$$
这就是第二问的答案了。因为分治中每次需要对 $[l,r]$ 之间的元素暴力排序，所以复杂度会多一个 $log$ ，也就是 $\mathcal{O}(n\log{}n)$
wa点：
- 虽然写的有点久但是没有wa点，一发yes O(∩_∩)O
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int mod=1e9+7;
struct node {
int id,h,v;
bool operator<(const struct node& rhs)const{
return h<rhs.h;
}
}ns[maxn],ps[maxn];
int n,h[maxn],v[maxn];
struct TreeArray
{
int mxbt[maxn-2];
double kdbt[maxn-2];//初始化都为0
int lowbit(int k){ return k&-k;}
void updatemax(int k,int val,double kinds){//种类数
while(k<=n){
if(mxbt[k] < val){
mxbt[k]=val;
kdbt[k]=kinds;
}
else if(mxbt[k] == val){
kdbt[k]+=kinds;
}
k+=lowbit(k);
}
}
int getpremax(int k,double &kinds){//返回mx<=k的最大长度和对应的种类数
int ans=-1;
kinds=0;
while(k){
if(mxbt[k] > ans){
ans=mxbt[k];
kinds=kdbt[k];
}
else if(mxbt[k]==ans)
kinds+=kdbt[k];
k-=lowbit(k);
}
return ans;
}
void en(int k){//add k的逆过程
while(k<=n){
mxbt[k]=0;
kdbt[k]=0;
k+=lowbit(k);
}
}
} hd;
int dpl[maxn],dpr[maxn],ca[maxn],ta[maxn];
double gl[maxn],gr[maxn];
void cdq1(int l,int r){
int (&dp)[maxn]=dpl;
double (&g)[maxn]=gl;
if(l==r){
dp[ns[l].id]=max(dp[ns[l].id],1);//if not calc then 1
g[ns[l].id]=max(g[ns[l].id],1.0);
return ;
}
int mid=(l+r)>>1,pl=l,pr=mid+1,tmpi;
double tmpd;
cdq1(l,mid);
for(int i=l;i<=r;++i) ps[i]=ns[i];
sort(ps+l,ps+mid+1);
sort(ps+mid+1,ps+r+1);
while(pl<=mid||pr<=r){
if(pl<=mid&&(r<pr||ps.h<=ps[pr].h)){
//add(ps.v,dp.id]);
hd.updatemax(ps.v,dp.id],g.id]);
++pl;
}
else{
//dp.id]=max(dp.id],ask(ps[pr].v)+1);
tmpi=hd.getpremax(ps[pr].v,tmpd)+1;
if(dp.id]<tmpi){
dp.id]=tmpi;
g.id]=tmpd;
}
else if(dp.id]==tmpi){
g.id]+=tmpd;
}else ;
++pr;
}
}
for(int i=l;i<=mid;++i) hd.en(ps[i].v);
cdq1(mid+1,r);
}
bool cmp(const node &a,const node &b){return a.h>b.h;}
void cdq2(int l,int r){
int (&dp)[maxn]=dpr;
double (&g)[maxn]=gr;
if(l==r){
dp[l]=max(dp[l],1);//if not calc then 1
g[l]=max(g[l],1.0);
return ;
}
int mid=(l+r)>>1,pl=l,pr=mid+1,tmpi;
double tmpd;
cdq2(l,mid);
for(int i=l;i<=r;++i) ps[i]=ns[i];
sort(ps+l,ps+mid+1,cmp);
sort(ps+mid+1,ps+r+1,cmp);
while(pl<=mid||pr<=r){
if(pl<=mid&&(r<pr||ps.h>=ps[pr].h)){
//add(ps.v,dp.id]);
hd.updatemax(ps.v,dp.id],g.id]);
++pl;
}
else{
//dp.id]=max(dp.id],ask(ps[pr].v)+1);
tmpi=hd.getpremax(ps[pr].v,tmpd)+1;
if(dp.id]<tmpi){
dp.id]=tmpi;
g.id]=tmpd;
}
else if(dp.id]==tmpi){
g.id]+=tmpd;
}else ;
++pr;
}
}
for(int i=l;i<=mid;++i) hd.en(ps[i].v);
cdq2(mid+1,r);
}
int hashx[maxn],cxt;
int Hashx(int x){return lower_bound(hashx+1,hashx+1+cxt,x)-hashx;}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&h[i],&v[i]),hashx[i]=v[i];
sort(hashx+1,hashx+1+n);cxt=1;for(int i=2;i<=n;++i) if(hashx[i]!=hashx[cxt]) hashx[++cxt]=hashx[i];//discrete
for(int i=1;i<=n;++i) ns[n+1-i].id=i,ns[n+1-i].h=h[i],ns[n+1-i].v=Hashx(v[i]);
cdq1(1,n);
for(int i=1;i<=n;++i) ns[i].id=i,ns[i].h=h[i],ns[i].v=cxt+1-Hashx(v[i]);
cdq2(1,n);
int ans=0;
double fm=0.0;
for(int i=1;i<=n;++i) ans=max(ans,dpl[i]);
for(int i=1;i<=n;++i) if(dpl[i]==ans) fm+=gl[i];
printf("%d\n",ans);
for(int i=1;i<=n;++i){
if(dpl[i]+dpr[i]-1==ans){
printf("%.12f ",gl[i]*gr[i]/fm);
}
else{
printf("0 ");
}
}
return 0;
}