题解

看了半天完全没发现这东西和CDQ有什么关系……

先把原序列翻转，求起来方便

然后把每一个位置表示成$(a,b,c)$其中$a$表示位置，$b$表示高度，$c$表示速度，求有多少个位置$a,b,c$都小于它，这就是一个三维偏序问题，直接CDQ就可以解决了……

然后考虑如何求第二问，就是一个导弹所在的LIS数/总的LIS数，因为一个导弹的LIS必须包含自己，以$g[i]$表示以$i$结尾的LIS总数，不难发现有如下转移式

$$g[i]=\sum g[j] \{ (i<j,h[i]<h[j],v[i]<v[j],f[j]+1=f[i]\}$$

这个也可以用CDQ来解决，只要统计出之前最大的LIS再和$f$比较就好了（完全没想出来怎么会这么神仙……）

然后再求出以$i$为开头的LIS长度和方案数，两个相乘就是他自己的方案数了

代码好长……调了好久……

1 //minamoto  2 #include
     
        3 using namespace std;  4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)  5 char buf[1<<21],*p1=buf,*p2=buf;  6 template
      
       inline bool cmax(T&a,const T&b){
   return a
       
        res.f) res=c[i]; 37         else if(c[i].f==res.f) res.w+=c[i].w; 38     } 39     return res; 40 } 41 struct node{ 42     int h,v,id,t; 43     int f[2];double g[2]; 44 }a[N],q[N]; 45 int wh[N],wv[N],id[N],rk[N]; 46 inline bool cmp(int i,int j) 47 {
   return a[i].h
        
         
          >1; 56     memcpy(q+l,a+l,sizeof(node)*(r-l+1)); 57     int q1=l,q2=mid+1; 58     for(int i=l;i<=r;++i){ 59         q[i].t<=mid?a[q1++]=q[i]:a[q2++]=q[i]; 60     } 61     solve(l,mid,t); 62     q1=l; 63     for(int i=mid+1;i<=r;++i){ 64         while(q1<=mid&&a[q1].id
          
           a[i].f[t]){ 68 a[i].f[t]=res.f+1,a[i].g[t]=res.w; 69 } 70 else if(res.f+1==a[i].f[t]) a[i].g[t]+=res.w; 71 } 72 while(top){c[st[top--]]=(BIT){ 0,0};} 73 solve(mid+1,r,t); 74 merge(a+l,a+mid+1,a+mid+1,a+r+1,q+l,cmpid); 75 memcpy(a+l,q+l,sizeof(node)*(r-l+1)); 76 } 77 int th=0,tv=0; 78 int main(){ 79 //freopen("testdata.in","r",stdin); 80 n=read(); 81 for(int i=1;i<=n;++i){ 82 wh[i]=a[i].h=read(),wv[i]=a[i].v=read(),a[i].id=i,rk[i]=i; 83 } 84 sort(wh+1,wh+1+n),sort(wv+1,wv+1+n); 85 th=unique(wh+1,wh+1+n)-wh-1,tv=unique(wv+1,wv+1+n)-wv-1; 86 for(int i=1;i<=n;++i){ 87 a[i].h=th-(lower_bound(wh+1,wh+th+1,a[i].h)-wh)+1; 88 a[i].v=tv-(lower_bound(wv+1,wv+tv+1,a[i].v)-wv)+1; 89 } 90 sort(rk+1,rk+1+n,cmp); 91 for(int i=1;i<=n;++i) a[rk[i]].t=i; 92 solve(1,n,0); 93 for(int i=1;i<=n;++i){ 94 a[i].h=th-a[i].h+1; 95 a[i].v=tv-a[i].v+1; 96 a[i].id=n-a[i].id+1; 97 a[i].t=n-a[i].t+1; 98 } 99 reverse(a+1,a+1+n);100 solve(1,n,1);101 reverse(a+1,a+1+n);102 double sum=0;int ans=0;103 for(int i=1;i<=n;++i){104 int len=a[i].f[0]+a[i].f[1]-1;105 cmax(ans,len);106 }107 printf("%d\n",ans);108 for(int i=1;i<=n;++i){109 if(a[i].f[0]==ans) sum+=a[i].g[0]*a[i].g[1];110 }111 for(int i=1;i<=n;++i){112 double res=a[i].g[0]*a[i].g[1];113 printf("%.5lf ",(a[i].f[0]+a[i].f[1]-1==ans)?(res/sum):0);114 }115 return 0;116 }