27WA 求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 50010
int n,dp[N],sum1[N],sum2[N],hs1[N],hs2[N],s1,s2,S,ddp[N];
struct fire{int h,v,id;}a[N];
struct Segments_tree{int l,r,dp_max,val;}tr[N<<2];
bool cmp1(fire x,fire y){return x.id<y.id;}
bool cmp2(fire x,fire y){if(x.h!=y.h)return x.h>y.h;return x.v>y.v;}
bool cmp3(fire x,fire y){return x.id>y.id;}
bool cmp4(fire x,fire y){if(x.h!=y.h)return x.h<y.h;return x.v<y.v;}
void pushup(int now){
	if(tr[now*2].dp_max>tr[now*2+1].dp_max)
		tr[now].dp_max=tr[now*2].dp_max,tr[now].val=tr[now*2].val;
	else if(tr[now*2].dp_max<tr[now*2+1].dp_max)
		tr[now].dp_max=tr[now*2+1].dp_max,tr[now].val=tr[now*2+1].val;
	else tr[now].dp_max=tr[now*2].dp_max,tr[now].val=tr[now*2].val+tr[now*2+1].val;
}
void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(now*2,l,mid),build(now*2+1,mid+1,r);
	pushup(now);
}
void update(int now,int where,int Dp,int Sum){
	if(tr[now].l==tr[now].r){tr[now].dp_max=Dp,tr[now].val=Sum;return;}
	if(where<=tr[now*2].r)update(now*2,where,Dp,Sum);
	else update(now*2+1,where,Dp,Sum);
	pushup(now);
}
struct node{int dp,sum;};
node query(int now,int l,int r){
	if(tr[now].r<l||r<tr[now].l)return {0,0};
	if(l<=tr[now].l&&tr[now].r<=r)return {tr[now].dp_max,tr[now].val};
	node A=query(now*2,l,r),B=query(now*2+1,l,r),ans;
	if(A.dp>B.dp)
		ans.dp=A.dp,ans.sum=A.sum;
	else if(A.dp<B.dp)
		ans.dp=B.dp,ans.sum=B.sum;
	else ans.dp=A.dp,ans.sum=A.sum+B.sum;
	return ans;
}
void CDQ1(int l,int r){
	if(l==r){return;}
	int mid=(l+r)>>1;
	CDQ1(l,mid);int pt=l;
	sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
	for(int i=mid+1;i<=r;i++){
		while(pt<=mid&&a[pt].h>=a[i].h)update(1,a[pt].v,dp[a[pt].id],sum1[a[pt].id]),++pt;
		node t=query(1,a[i].v,s2);
		if(!t.dp)continue;
		if(t.dp+1>dp[a[i].id])dp[a[i].id]=t.dp+1,sum1[a[i].id]=t.sum;
		else if(t.dp+1==dp[a[i].id])sum1[a[i].id]+=t.sum;
	}
	for(int i=l;i<pt;i++)update(1,a[i].v,0,0);
	sort(a+l,a+r+1,cmp1);
	CDQ1(mid+1,r);
}
void CDQ2(int l,int r){
	if(l==r){return;}
	int mid=(l+r)>>1;
	CDQ2(l,mid);int pt=l;
	sort(a+l,a+mid+1,cmp4),sort(a+mid+1,a+r+1,cmp4);
	for(int i=mid+1;i<=r;i++){
		while(pt<=mid&&a[pt].h<=a[i].h)update(1,a[pt].v,dp[a[pt].id],sum2[a[pt].id]),++pt;
		node t=query(1,1,a[i].v);
		if(!t.dp)continue;
		if(t.dp+1>dp[a[i].id])dp[a[i].id]=t.dp+1,sum2[a[i].id]=t.sum;
		else if(t.dp+1==dp[a[i].id])sum2[a[i].id]+=t.sum;
	}
	for(int i=l;i<pt;i++)update(1,a[i].v,0,0);
	sort(a+l,a+r+1,cmp3);
	CDQ2(mid+1,r);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].h>>a[i].v,hs1[i]=a[i].h,hs2[i]=a[i].v,a[i].id=i,sum1[i]=sum2[i]=1;
	sort(hs1+1,hs1+1+n);s1=unique(hs1+1,hs1+1+n)-hs1-1;
	sort(hs2+1,hs2+1+n);s2=unique(hs2+1,hs2+1+n)-hs2-1;
	for(int i=1;i<=n;i++)a[i].h=lower_bound(hs1+1,hs1+1+s1,a[i].h)-hs1;
	for(int i=1;i<=n;i++)a[i].v=lower_bound(hs2+1,hs2+1+s2,a[i].v)-hs2;
	for(int i=1;i<=n;i++)dp[i]=1;
	build(1,1,s2);
	CDQ1(1,n);
	int Mx=0;
	for(int i=1;i<=n;i++)Mx=max(Mx,dp[i]);
	for(int i=1;i<=n;i++)if(dp[i]==Mx)S+=sum1[i];
	sort(a+1,a+1+n,cmp3);
	for(int i=1;i<=n;i++)ddp[i]=dp[i],dp[i]=1;
	CDQ2(1,n);
	cout<<Mx<<'\n';
	for(int i=1;i<=n;i++){
		if(ddp[i]+dp[i]-1==Mx){
			cout<<fixed<<setprecision(5)<<sum1[i]*1.0/S*sum2[i]<<' ';
		}
		else cout<<0<<' ';
	}
	return 0;
}