求求求求求调

#include <bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
struct node{
    int h,v,id;
    int rkv;
}a[50005],tp[50005];
struct shu{
    int len;
    double cnt;
}bits[50005];
int p[50005],q[50005],n,m=0,dp1[50005],dp2[50005];
double f1[50005],f2[50005],tmpf[50005];
int gi(int x){
	int l=1,r=m;
	while(l<=r){
		int mid=(l+r)/2;
		if(q[mid]==x) return mid;
		else if(q[mid]>x) r=mid-1;
		else l=mid+1;
	}
	return 0;
}
void init(){
	for(int i=1;i<=n;i++){
		p[i]=a[i].v;
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
        if(i==1||p[i-1]!=p[i]){
            q[++m]=p[i];
        }
	}
    for(int i=1;i<=n;i++){
        a[i].rkv=m-gi(a[i].v)+1;
    }
}
bool my_cmp(node x,node y){
    if(x.h!=y.h) return x.h>y.h;
    else return x.id<y.id;
}
void update2(int x,int y,int z){
    for(;x<=m;x+=lowbit(x)){
        if(y>bits[x].len){
            bits[x].len=y;
            bits[x].cnt=z;
        }else if(y==bits[x].len){
            bits[x].cnt+=z;
        }
    }
}
void clear2(int x){
    for(;x<=m;x+=lowbit(x)){
        bits[x].len=0;
        bits[x].cnt=0;
    }
}
shu query2(int x){
    shu ans={0,0};
    for(;x>=1;x-=lowbit(x)){
        if(ans.len<bits[x].len){
            ans.len=bits[x].len;
            ans.cnt=bits[x].cnt;
        }else if(ans.len==bits[x].len){
            ans.cnt+=bits[x].cnt;
        }
    }
    return ans;
}
void cdqf(int l,int r,int dp[],double f[]){
    node tmp[50005];
    if(l==r) return;
    int mid=(l+r)/2;
    // 1. 先递归左边
    cdqf(l,mid,dp,f);
    // 2. 处理左边对右边的影响
    for(int i=l;i<=r;i++){
        tmp[i].h=a[i].h;
        tmp[i].v=a[i].v;
        tmp[i].id=a[i].id;
        tmp[i].rkv=a[i].rkv;
    }
    sort(tmp+l,tmp+mid+1,my_cmp);
    sort(tmp+mid+1,tmp+r+1,my_cmp);
    int j=l;
    for(int i=mid+1;i<=r;i++){
        while(j<=mid&&tmp[j].h>=tmp[i].h){
            update2(tmp[j].rkv,dp[tmp[j].id],f[tmp[j].id]);
            j++;
        }
        shu t=query2(tmp[i].rkv);
        if(dp[tmp[i].id]<t.len+1){
            dp[tmp[i].id]=t.len+1;
            f[tmp[i].id]=t.cnt;
        }else if(dp[tmp[i].id]==t.len+1){
            f[tmp[i].id]+=t.cnt;
        }
    }
    for(int i=l;i<=mid;i++){
        clear2(tmp[i].rkv);
    }
    // 3. 再递归右边
    cdqf(mid+1,r,dp,f);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].h>>a[i].v;
        a[i].id=i;
        dp1[i]=dp2[i]=1;
        f1[i]=f2[i]=1.0;
    }
    init();
    cdqf(1,n,dp1,f1);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp1[i]);
    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++){
        tp[i].h=a[n-i+1].h;
        tp[i].v=a[n-i+1].v;
        tp[i].rkv=a[n-i+1].rkv;
        tp[i].id=a[n-i+1].id;
    }
    for(int i=1;i<=n;i++){
        a[i].h=tp[i].h;
        a[i].v=tp[i].v;
        a[i].rkv=tp[i].rkv;
        a[i].id=tp[i].id;
    }
    memset(bits,0,sizeof(bits));
    cdqf(1,n,dp2,f2);
    for(int i=1;i<=n;i++){
        p[i]=dp2[n-i+1];
    }
    for(int i=1;i<=n;i++){
        dp2[i]=p[i];
    }
    //memset(bits,0,sizeof(bits));
    for(int i=1;i<=n;i++){
        tmpf[i]=f2[n-i+1];
    }
    for(int i=1;i<=n;i++){
        f2[i]=tmpf[i];
    }
    double tot=0;
    for(int i=1;i<=n;i++){
        if(dp1[i]+dp2[i]-1==ans){
            tot+=f1[i]*f2[i];
        }
    }
    for(int i=1;i<=n;i++){
        if(dp1[i]+dp2[i]-1==ans){
            printf("%.5lf ",f1[i]*f2[i]/tot);
        }else{
            cout<<"0.00000 ";
        }
    }
}