1. 题目

传送门=￣ω￣=

2. 题解

我太菜了 QwQ 我不会 CDQ

首先这个问题的第一问就是一个典型的三维偏序问题

三维偏序的最长不升子序列问题

CDQ 分治第一维（导弹飞来的时间），第二维排序（导弹高度），第三维树状数组。

如果 $i$能从 $j$转移过来，则：

$f[i] = max\{ f[j] \} + 1$

（可以，这个递推式很 CY）

树状数组维护一下前缀最大值就行了。

第二问求概率的话，就是要求出有多少个最长不升子序列经过该点。

则可以求出 “以这个点为结尾的最长不升子序列个数$f$” 和 “以这个点为开头的最长不升子序列个数$g$”

如果 “以这个点为结尾的最长不升子序列的长度” 加 “以这个点为开头的最长不升子序列长度” 等于第一个答案加一（加一是因为该点计算了两遍），则经过该点的最长不升子序列的个数就是 $f \times g$

所以做两遍 CDQ 就行了。

第二遍的时候把数组翻转一下，然后把数值也翻转一下，问题就和第一遍 CDQ 时的一样了。

代码：

#include <bits/stdc++.h>

#define NS (50005)
#define lowbit(a) (a & -a)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct Pac {int x, y, i;};

bool cmp(Pac a, Pac b) {return a.x > b.x;}

int n, h[NS], hs, f[NS], u[NS], tf[NS];

double g[NS], o[NS], tg[NS], sum;

Pac P[NS], T[NS];

void Add(int a)
{
    int x = T[a].y;
    while (x <= hs)
    {
        if (f[T[a].i] > tf[x]) tf[x] = f[T[a].i], tg[x] = g[T[a].i];
        else if (f[T[a].i] == tf[x]) tg[x] += g[T[a].i];
        x += lowbit(x);
    }
}

void Query(int x, int& t1, double& t2)
{
    t1 = t2 = 0;
    while (x)
    {
        if (tf[x] > t1) t1 = tf[x], t2 = tg[x];
        else if (tf[x] == t1) t2 += tg[x];
        x -= lowbit(x);
    }
    t1++;
}

void Clear(int x)
{
    while (x <= hs) tf[x] = tg[x] = 0, x += lowbit(x);
}

void Div(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    Div(l, mid);
    for (int i = l; i <= r; i += 1) T[i] = P[i];
    sort(T + l, T + mid + 1, cmp), sort(T + mid + 1, T + r + 1, cmp);
    int x = l, y = mid + 1;
    while (y <= r)
    {
        while (x <= mid && T[x].x >= T[y].x) Add(x), x++;
        int t1; double t2; Query(T[y].y, t1, t2);
        if (t1 > f[T[y].i]) f[T[y].i] = t1, g[T[y].i] = t2;
        else if (t1 == f[T[y].i]) g[T[y].i] += t2;
        y++;
    }
    for (int i = l; i <= mid; i += 1) Clear(T[i].y);
    Div(mid + 1, r);
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1)
        IN(P[i].x), IN(P[i].y), P[i].i = i, h[i] = P[i].y;
    sort(h + 1, h + 1 + n);
    for (int i = 1; i <= n; i += 1) if (h[i] != h[i - 1]) h[++hs] = h[i];
    for (int i = 1; i <= n; i += 1)
        P[i].y = hs - (lower_bound(h + 1, h + 1 + hs, P[i].y) - h) + 1;
    for (int i = 1; i <= n; i += 1) f[i] = g[i] = 1;
    Div(1, n); int len = *max_element(f + 1, f + 1 + n);
    for (int i = 1; i <= n; i += 1) if (f[i] == len) sum += g[i];
    memmove(u, f, sizeof(u)), memmove(o, g, sizeof(o));
    for (int i = 1; i <= n; i += 1) f[i] = g[i] = 1;
    for (int i = 1, j = n; i < j; i += 1, j -= 1) swap(P[i], P[j]);
    for (int i = 1; i <= n; i += 1) P[i].x = -P[i].x, P[i].y = hs - P[i].y + 1;
    Div(1, n), printf("%d\n", len);
    for (int i = 1; i <= n; i += 1)
        if (u[i] + f[i] - 1 == len) printf("%.5lf ", o[i] * g[i] / sum);
        else printf("0.00000 ");
    putchar(10);
    return 0;
}