2. 题解

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

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

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

#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];

{
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;
}