思路：
正反两个 CDQ ，
ll[i] // 从左到右最长序列 rr[i] // 从右到左最长序列 lnum[i] //包含 i 这个数，有多少个最优方案，从左到右 rnum[i] //包含 i 这个数，有多少个最优方案， 从右到左。
这个题首先要离散化， CDQ 我们先 递归先找左面的， 然后当前点的， 最后递归找右面的。（这个是第一遍 CDQ ，第二遍CDQ 我们要从右向左找。） 然后正着一遍 CDQ ，求出来从左到右的最长序列，以及选了这个点的方案数。 然后倒着一遍 CDQ ，求出来从右到左的最长序列，以及选了这个点的方案数。 最终答案就是 (lnum[i] * rnum[i] / ans), ans 是总的最优方案数。 我们用CDQ 的时候，需要用 线段树维护两个值， 一个是最长序列，一个是满足最长序列有多少个方案。 方案数随着 最长序列的改变而改变。
#include<bits/stdc++.h> #define ls (now << 1) #define rs (now << 1 | 1) using namespace std; const int N = 5e4+100; typedef long long LL; int n; LL a[N],b[N],cnt,d[N],e[N],c[N]; struct node{ LL a,b,id; bool vis; }f[N]; LL ll[N],rr[N]; LL val[4*N],ans1,len; double sum[4*N],ans2,lnum[N],rnum[N],ans; bool cmp1(const node &A, const node &B){ if (A.a != B.a) return A.a > B.a; if (A.b != B.b) return A.b > B.b; return A.vis < B.vis; } bool cmp2(const node &A, const node &B){ if (A.a != B.a) return A.a < B.a; if (A.b != B.b) return A.b < B.b; return A.vis < B.vis; } void build(int now, int l, int r){ if (val[now] == 0) return; val[now] = 0; if (l + 1 == r) return; int mid = (l + r) >> 1; build(ls,l,mid); build(rs,mid,r); } void init(){ for (int i = 0; i <= n; ++i){ lnum[i] = rnum[i] = 1.0; ll[i] = rr[i] = 1; } sort(d+1,d+n+1); sort(e+1,e+n+1); int cnt1 = unique(d+1,d+n+1) - (d + 1); int cnt2 = unique(e+1,e+n+1) - (e + 1); for (int i = 1; i <= n; ++i){ a[i] = lower_bound(d+1,d+cnt1+1,a[i]) - d; b[i] = lower_bound(e+1,e+cnt2+1,b[i]) - e; } } void Insert(int now, int l, int r, LL a, LL b, LL k, double w){ if (a <= l && b >= r - 1){ if (k > val[now]) val[now] = k,sum[now] = 0; if (k == val[now]) sum[now] += w; return; } int mid = (l + r) >> 1; if (a < mid) Insert(ls,l,mid,a,b,k,w); if (b >= mid) Insert(rs,mid,r,a,b,k,w); val[now] = max(val[ls],val[rs]); sum[now] = 0; if (val[ls] == val[now]) sum[now] += sum[ls]; if (val[rs] == val[now]) sum[now] += sum[rs]; } void Query(int now, int l, int r, LL a, LL b){ if (a <= l && b >= r - 1){ if (val[now] > ans1) ans1 = val[now], ans2 = 0; if (val[now] == ans1) ans2 += sum[now]; return; } int mid = (l + r) >> 1; if (a < mid) Query(ls, l, mid ,a,b); if (b >= mid) Query(rs, mid, r, a,b); } void CDQ1(int l, int r){ if (l >= r) return; int mid = (l + r) >> 1,tot = 0; CDQ1(l,mid); build(1,1,n+1); for (int i = l; i <= mid; ++i){ f[tot].id = i; f[tot].a = a[i]; f[tot].b = b[i]; f[tot++].vis = 0; } for (int i = mid + 1; i <= r; ++i){ f[tot].id = i; f[tot].a = a[i]; f[tot].b = b[i]; f[tot++].vis = 1; } sort(f,f+tot,cmp1); for (int i = 0; i < tot; ++i){ if (f[i].vis == 0) Insert(1,1,n+1,f[i].b,f[i].b,ll[f[i].id],lnum[f[i].id]); else{ ans1 = ans2 = 0; Query(1,1,n+1,f[i].b,n); if (ans1 == 0) continue; if (ll[f[i].id] < ans1 + 1) ll[f[i].id] = ans1 + 1, lnum[f[i].id] = 0; if (ll[f[i].id] == ans1 + 1) lnum[f[i].id] += ans2; } } CDQ1(mid+1,r); } void CDQ2(int l, int r){ if (l >= r) return; int mid = (l + r) >> 1, tot = 0; CDQ2(mid+1,r); build(1,1,n+1); for (int i = r; i > mid; --i){ f[tot].id = i; f[tot].a = a[i]; f[tot].b = b[i]; f[tot++].vis = 0; } for (int i = mid; i >= l; --i){ f[tot].id = i; f[tot].a = a[i]; f[tot].b = b[i]; f[tot++].vis = 1; } sort(f,f+tot,cmp2); for (int i = 0; i < tot; ++i){ if (f[i].vis == 0) Insert(1,1,n+1,f[i].b,f[i].b,rr[f[i].id],rnum[f[i].id]); else{ ans1 = ans2 = 0; Query(1,1,n+1,1,f[i].b); if (ans1 == 0) continue;// 切记。如果ans1是0那么不需要更改。有且只有一个方案。 if (rr[f[i].id] < ans1 + 1) rr[f[i].id] = ans1 + 1, rnum[f[i].id] = 0; if (rr[f[i].id] == ans1 + 1) rnum[f[i].id] += ans2; } } CDQ2(l,mid); } int main(){ scanf("%d",&n); for (int i = 1; i <= n; ++i){ scanf("%lld%lld",&a[i],&b[i]); d[i] = a[i]; e[i] = b[i]; } init(); CDQ1(1,n); CDQ2(1,n); for (int i = 1; i <= n; ++i) len = max(len,ll[i]); for (int i = 1; i <= n; ++i) if (ll[i] == len) ans += lnum[i]; printf("%lld\n",len); for (int i = 1; i <= n; ++i){ if (ll[i] + rr[i] - 1 == len) printf("%.5lf ",lnum[i]*rnum[i]/ans); else{ printf("%.5lf ",0.0); } } return 0; } /* 4 3 30 4 40 6 60 3 30 6 4 25 4 30 4 35 4 40 4 45 4 50 */
