题意：求出一个序列 \(q\) 的最长二维不上升子序列，以及求出每个数出现在这个最长二维不上升子序列中的概率。
很显然，三维偏序问题可以用 cdq 分治来优化 dp。
对于第一问，直接把这道题的 \(n^{2}\) dp 优化到 \(\log^{2}\) 即可。具体来讲，设 \(l_{i}\) 表示以 \(q_{i}\) 结尾的最长二维不上升子序列的长度，\(r_{i}\) 以 \(q_{i}\) 开头的最长二维不上升子序列的长度，则答案就是 \(\sum l_{i}\)（\(r_{i}\) 的作用最后会讲）。
本题的难点在第二问。我们知道，\(q_{i}\) 出现在序列中出现的概率应该等于包含 \(q_{i}\) 的最长二维不上升子序列的个数（一），除以所有最长二维不上升子序列的个数（二）。对于（一），我们可以维护两个数组 \(p,q\) 分别表示以 \(q_{i}\) 结尾的最长二维不上升子序列的个数和以 \(q_{i}\) 开头的最长二维不上升子序列的个数，那么（一）就等于 \(p_{i} \times q_{i}\)，因为前后可以两两组合。而总数就是 \(\sum p_{i}[l_{i}==ans]\)。
注意：选到当前这个数的概率不为 \(0\) 的时候，必须满足 \(l_{i}+r_{i}=ans+1\) 才行，因为只有满足这个才能保证包含当前点的最长二维不上升子序列的长度和答案相同。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e4 + 10;
int n,dp1[MAXN],dp2[MAXN],tree1[MAXN];
double tree2[MAXN],f2[MAXN],f1[MAXN];
struct Node{int x,y,z,dp;double f;}q[MAXN];
inline int Lowbit(int x){return (x & -x);}
inline void Update(int x,int dp,double f)
{
for(;x <= n;x += Lowbit(x))
{
if(tree1[x] < dp) tree1[x] = dp,tree2[x] = f;
else if(tree1[x] == dp) tree2[x] += f;
}
}
inline int Query_dp(int x)
{
int res = 0;
for(;x >= 1;x -= Lowbit(x)) res = max(res,tree1[x]);
return res;
}
inline double Query_f(int x,int dp)
{
double res = 0;
for(;x >= 1;x -= Lowbit(x)) if(tree1[x] == dp) res += tree2[x];
return res;
}
inline void Clear(int x){for(;x <= n;x += Lowbit(x)) tree1[x] = tree2[x] = 0;}
inline bool cmp2(Node x,Node y)
{
if(x.x != y.x) return x.x < y.x;
if(x.y != y.y) return x.y < y.y;
return x.z < y.z;
}
inline bool cmp1(Node x,Node y)
{
if(x.x != y.x) return x.x > y.x;
if(x.y != y.y) return x.y > y.y;
return x.z < y.z;
}
inline bool cmp4(Node x,Node y){return x.y < y.y;}
inline bool cmp3(Node x,Node y){return x.y > y.y;}
inline bool check(int i,int j,int op)
{
if(op == 1) return q[i].y >= q[j].y;
if(op == 2) return q[i].y <= q[j].y;
}
inline void solve(int l,int r,int op)
{
int mid = (l + r) >> 1;
int i = l,j = mid + 1;
while(i <= mid && j <= r)
{
if(check(i,j,op)) Update(q[i].z,q[i].dp,q[i].f),i++;
else
{
int tmp = Query_dp(q[j].z) + 1;
if(q[j].dp < tmp) q[j].dp = tmp,q[j].f = Query_f(q[j].z,q[j].dp - 1);
else if(q[j].dp == tmp) q[j].f += Query_f(q[j].z,q[j].dp - 1);
j++;
}
}
while(j <= r)
{
int tmp = Query_dp(q[j].z) + 1;
if(q[j].dp < tmp) q[j].dp = tmp,q[j].f = Query_f(q[j].z,q[j].dp - 1);
else if(q[j].dp == tmp) q[j].f += Query_f(q[j].z,q[j].dp - 1);
j++;
}
for(int k = l;k < i;k++) Clear(q[k].z);
}
inline void cdq(int l,int r,int op)
{
if(l >= r) return;
int mid = (l + r) >> 1;
cdq(l,mid,op);
if(op == 1) sort(q + l,q + mid + 1,cmp3),sort(q + mid + 1,q + r + 1,cmp3);
if(op == 2) sort(q + l,q + mid + 1,cmp4),sort(q + mid + 1,q + r + 1,cmp4);
solve(l,r,op);
if(op == 1) sort(q + mid + 1,q + r + 1,cmp1);
if(op == 2) sort(q + mid + 1,q + r + 1,cmp2);
cdq(mid + 1,r,op);
}
signed main()
{
cin >> n;
for(int i = 1;i <= n;i++) cin >> q[i].x >> q[i].y,q[i].z = i;
for(int i = 1;i <= n;i++) q[i].f = q[i].dp = 1;
sort(q + 1,q + n + 1,cmp1),cdq(1,n,1);
int ans = 0;
for(int i = 1;i <= n;i++)
{
dp1[q[i].z] = q[i].dp;
f1[q[i].z] = q[i].f;
ans = max(ans,dp1[q[i].z]);
}
cout << ans << endl;
for(int i = 1;i <= n;i++) q[i].z = n - q[i].z + 1;
for(int i = 1;i <= n;i++) q[i].f = q[i].dp = 1;
sort(q + 1,q + n + 1,cmp2),cdq(1,n,2);
double k = 0;
for(int i = 1;i <= n;i++)
{
dp2[n - q[i].z + 1] = q[i].dp;
f2[n - q[i].z + 1] = q[i].f;
if(dp2[n - q[i].z + 1] == ans) k += f2[n - q[i].z + 1];
}
for(int i = 1;i <= n;i++)
{
if(dp1[i] + dp2[i] == ans + 1) printf("%.5lf ",f1[i] * f2[i] / k);
else printf("0.0000000 ");
}
return 0;
}