Problem Summary

We are given a sequence of n missiles, each defined by two attributes: height h[i] and speed v[i]. A missile can intercept another if its height and speed are both less than or equal to the target's. We are to calculate the probability of each missile being part of a longest non-increasing subsequence (LNDS), assuming we randomly select one such sequence. Constraints: - 1 ≤ n ≤ 5×10⁴

• 1 ≤ h[i], v[i] ≤ 10⁹

Core Concepts

We define: - f1[i]: Length of the LNDS ending at i

• g1[i]: Number of LNDS sequences ending at i
• f2[i]: Length of LNDS starting at i
• g2[i]: Number of LNDS sequences starting at i
• k: Total number of LNDS in the sequence

The probability that missile i appears in a random LNDS is: ``` probability[i] = (g1[i] * g2[i]) / k

### Optimization Strategy

A brute-force DP solution would take `O(n²)` time. To reduce complexity, we use: - Cross-division divide and conquer (cdq)
- Coordinate compression for speed values
- Segment tree for efficient range queries

### Algorithm Steps

1. Compress speed values to reduce range
2. Compute `f1` and `g1` using cdq divide and conquer
3. Reverse and transform the sequence to compute `f2` and `g2`
4. Calculate the total number of LNDS `k`
5. Compute probabilities for each missile

### cdq Divide and Conquer Details

To a range `[l, r]`: 1. Recursively solve the left half `[l, m]`
2. Use a segment tree to update values from the left half and query against the right half
3. Recursively solve the right half `(m, r]`

Sorting is essential at each step to ensure correct ordering of operattions. ### Code Impleemntation

```html ```

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 5e4 + 5;

struct Missile {
    int f, pos, height, speed;
    double count;
} missiles[MAXN], backup[MAXN];

struct SegmentTreeNode {
    int left, right, maxValue;
    double total;
} tree[MAXN << 2];

int n, speedLimit;
int temp[MAXN], f1[MAXN], f2[MAXN];
double g1[MAXN], g2[MAXN];

bool compareByHeight(Missile a, Missile b) {
    return a.height > b.height;
}

bool compareByPosition(Missile a, Missile b) {
    return a.pos < b.pos;
}

void buildTree(int node, int l, int r) {
    tree[node].left = l;
    tree[node].right = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    buildTree(node << 1, l, mid);
    buildTree(node << 1 | 1, mid + 1, r);
}

void update(int node, int position, int value, double total) {
    if (tree[node].left == tree[node].right) {
        if (tree[node].maxValue < value) tree[node].total = 0;
        tree[node].maxValue = max(tree[node].maxValue, value);
        if (tree[node].maxValue == value) tree[node].total += total;
        return;
    }
    int mid = (tree[node].left + tree[node].right) >> 1;
    if (position <= mid) update(node << 1, position, value, total);
    else update(node << 1 | 1, position, value, total);
    tree[node].maxValue = max(tree[node << 1].maxValue, tree[node << 1 | 1].maxValue);
    tree[node].total = 0;
    if (tree[node].maxValue == tree[node << 1].maxValue) 
        tree[node].total += tree[node << 1].total;
    if (tree[node].maxValue == tree[node << 1 | 1].maxValue) 
        tree[node].total += tree[node << 1 | 1].total;
}

void clearTree(int node) {
    if (!tree[node].maxValue) return;
    tree[node].maxValue = tree[node].total = 0;
    if (tree[node].left != tree[node].right) {
        clearTree(node << 1);
        clearTree(node << 1 | 1);
    }
}

pair<int double=""> query(int node, int l, int r) {
    if (tree[node].left >= l && tree[node].right <= r)
        return make_pair(tree[node].maxValue, tree[node].total);
    int mid = (tree[node].left + tree[node].right) >> 1;
    pair<int double=""> leftResult = make_pair(0, 0), rightResult = make_pair(0, 0);
    if (l <= mid) leftResult = query(node << 1, l, r);
    if (r > mid) rightResult = query(node << 1 | 1, l, r);
    if (leftResult.first > rightResult.first) return leftResult;
    if (rightResult.first > leftResult.first) return rightResult;
    return make_pair(leftResult.first, leftResult.second + rightResult.second);
}

void cdqDivideConquer(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    sort(missiles + l, missiles + r + 1, compareByPosition);
    cdqDivideConquer(l, mid);
    clearTree(1);
    sort(missiles + l, missiles + mid + 1, compareByHeight);
    sort(missiles + mid + 1, missiles + r + 1, compareByHeight);
    int i = mid + 1, j = l;
    while (i <= r) {
        while (j <= mid && missiles[j].height >= missiles[i].height) {
            update(1, missiles[j].speed, missiles[j].f, missiles[j].count);
            j++;
        }
        pair<int double=""> result = query(1, missiles[i].speed, speedLimit);
        if (result.first) {
            if (missiles[i].f < result.first + 1) missiles[i].count = 0;
            missiles[i].f = max(missiles[i].f, result.first + 1);
            missiles[i].count += (missiles[i].f == result.first + 1 ? 1 : 0) * result.second;
        }
        i++;
    }
    cdqDivideConquer(mid + 1, r);
}

int main() {
    int maxLength = 0;
    double total = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        missiles[i].pos = i;
        scanf("%d%d", &missiles[i].height, &missiles[i].speed);
        temp[i] = missiles[i].speed;
    }
    sort(temp + 1, temp + n + 1);
    speedLimit = unique(temp + 1, temp + n + 1) - temp - 1;
    buildTree(1, 1, speedLimit);
    for (int i = 1; i <= n; i++) {
        missiles[i].speed = lower_bound(temp + 1, temp + speedLimit + 1, missiles[i].speed) - temp;
        missiles[i].f = missiles[i].count = 1;
        backup[i] = missiles[i];
    }
    cdqDivideConquer(1, n);
    for (int i = 1; i <= n; i++) maxLength = max(maxLength, missiles[i].f);
    for (int i = 1; i <= n; i++) if (missiles[i].f == maxLength) total += missiles[i].count;
    for (int i = 1; i <= n; i++) {
        f1[missiles[i].pos] = missiles[i].f;
        g1[missiles[i].pos] = missiles[i].count;
        missiles[i] = backup[n - i + 1];
        missiles[i].height = 1e9 - missiles[i].height + 1;
        missiles[i].speed = speedLimit - missiles[i].speed + 1;
        missiles[i].pos = n - missiles[i].pos + 1;
    }
    cdqDivideConquer(1, n);
    for (int i = 1; i <= n; i++) {
        f2[n - missiles[i].pos + 1] = missiles[i].f;
        g2[n - missiles[i].pos + 1] = missiles[i].count;
    }
    printf("%d\n", maxLength);
    for (int i = 1; i <= n; i++) {
        if (f1[i] + f2[i] - 1 == maxLength)
            printf("%.6lf ", g1[i] * g2[i] / total);
        else
            printf("%.6lf ", 0.0);
    }
    return 0;
}
</int></int></int>