https://www.luogu.com.cn/record/226602029

cdq跑起来按说应该绰绰有余，结果TLE 95pts，而且后面几个点已经在爆T边缘了。。。一定是哪里的细节有问题，但是实在找不出来了，求助(-_-

//(i,a_i,b_i)
//i用树状数组维护
//a_i排序
//b_i分治
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,f[2][N];
bool flg;
struct Node{int id,a,b;}a[N],t[N];
double sum,g[2][N];
inline int lb(int x){return x&-x;}
struct BIT{
	int mx[N];double c[N];
	void chp(int x,int _mx,double _c){for(;x<=n;x+=lb(x)) if(_mx==mx[x]) c[x]+=_c;else if(_mx>mx[x]) c[x]=_c,mx[x]=_mx;}
	void clr(int x){for(;x<=n;x+=lb(x)) if(mx[x]) mx[x]=c[x]=0;else break;}
	void qry(int x,int &_mx,double &_c){
		_mx=_c=0;
		for(;x;x-=lb(x)) if(mx[x]==_mx) _c+=c[x];else if(mx[x]>_mx) _c=c[x],_mx=mx[x];
	}
}bit;
inline bool cmpb(Node a,Node b){return flg?a.b<b.b:a.b>b.b;}
inline bool cmpa(Node a,Node b){
	return a.a==b.a?(a.b==b.b?a.id<b.id:cmpb(a,b)):(flg?a.a<b.a:a.a>b.a);
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1,i,j,mx;double c;
	cdq(l,mid);
	sort(a+l,a+mid+1,cmpb),sort(a+mid+1,a+r+1,cmpb);
	for(i=l,j=mid+1;j<=r;j++){
		while(i<=mid&&(a[i].b==a[j].b||cmpb(a[i],a[j]))) bit.chp(a[i].id,f[flg][a[i].id],g[flg][a[i].id]),i++;
		bit.qry(a[j].id-1,mx,c);
		if(mx+1==f[flg][a[j].id]) g[flg][a[j].id]+=c;
		else if(mx+1>f[flg][a[j].id]) f[flg][a[j].id]=mx+1,g[flg][a[j].id]=c;
	}
	for(i=1;i<=mid;i++) bit.clr(a[i].id);
	sort(a+mid+1,a+r+1,cmpa),cdq(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].a>>a[i].b,a[i].id=i,g[0][i]=g[1][i]=f[0][i]=f[1][i]=1;
	flg=0,sort(a+1,a+1+n,cmpa),cdq(1,n);
	for(int i=1;i<=n;i++) a[i].id=n-a[i].id+1;
	flg=1,sort(a+1,a+1+n,cmpa),cdq(1,n);//由于id反转，所以f[1],g[1]也是反着存的
	int mx=*max_element(f[0]+1,f[0]+n+1);
	for(int i=1;i<=n;i++) if(f[0][i]==mx) sum+=g[0][i];
	cout<<mx<<"\n";
	for(int i=1;i<=n;i++){
		if(f[0][i]+f[1][n-i+1]-1==mx) cout<<fixed<<setprecision(5)<<g[0][i]*g[1][n-i+1]/sum<<" ";
		else cout<<"0.00000 ";
	}
	return 0;
}