洛谷P2487 [SDOI2011] 拦截导弹题解

题目链接：P2487 [SDOI2011] 拦截导弹

题意：

注意本题不是 P1020 [NOIP1999 提高组] 导弹拦截，本题有额外的速度限制（~~更科学了~~）。

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

输入格式：

第一行包含一个正整数 $n$，表示敌军导弹数量。

下面 $n$ 行按顺序给出了敌军所有导弹信息。

第 $i+1$ 行包含两个正整数 $h_i$ 和 $v_i$，分别表示第 $i$ 枚导弹的高度和速度。

输出格式：

输出包含两行。

第一行为一个正整数，表示最多能拦截掉的导弹数量；

第二行包含 $n$ 个 $0$ 到 $1$ 之间的实数，第 $i$ 个数字表示第 $i$ 枚导弹被拦截的概率。误差应当小于 $10^{-4}$ 。

数据范围：

$1\le n\le 5\times 10^4$，$1\le h_i,v_i\le 10^9$。保证总方案数不超过 C++ 中 double 类型的存储范围。

设 $f_i$ 表示以 $i$ 结尾的最长不上升子序列的长度，$g_i$ 表示以 $i$ 开头的最长不上升子序列的长度，则

$\begin{array}{l} f_i = \max \{f_j\} + 1 && j < i \,\land \,h_i \ge h_j \, \land \, v_i \ge v_j \\[8pt]g_i = \max \{g_j\} + 1 && j > i \,\land \,h_i \le h_j \, \land \, v_i \le v_j \end{array}$

设 $F_i$ 表示以 $i$ 结尾的最长不上升子序列的数量，$G_i$ 表示以 $i$ 开头的最长不上升子序列的数量。

考虑转移。记 $\mathrm{mx} = \max\{f_i\}$ ，则

$\begin{array}{l} F_i = \sum F_j && j < i \,\land\, h_i \ge h_j \,\land\, v_i \ge v_j\, \land \,f_j=\mathrm{mx} - 1 \\[8pt] G_i = \sum G_j && j > i \,\land\, h_i \le h_j \,\land\, v_i \le v_j\, \land \,g_j=\mathrm{mx} - 1 \end{array}$

转移方程都这么写了应该看出来了吧，这就是一个三维偏序，考虑 CDQ 分治优化dp。

那么第一问的答案就是 $\rm mx$ ，第二问第 $i$ 枚导弹的概率为

$\frac{F_i\times G_i \times [f_i + g_i = \mathrm{mx}-1]}{\sum_{j=1}^n [f_j =\mathrm{mx}]}$

其中 $\mathrm{mx} - 1$ 是因为多算了一次 $i$ ，还有式子里的中括号是艾弗森括号 (Iverson bracket) 。

提示：这种不等式里可以取等的情况在排序的时候要注意。（是谁调了半天？我不会说的。）

时间复杂度 $\mathcal{O}(n \log^2 n)$

代码：（代码里的 dp1,dp2 就是上面讲的 $f,g$ ）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e4 + 15))

int n, dp1[N], dp2[N], tr1[N];
double f1[N], f2[N], tr2[N];
struct node{ int x, y, z, dp; double f; } a[N];
bool cmp1(node x, node y) { return x.x == y.x ? (x.y == y.y ? x.z < y.z : x.y > y.y) : x.x > y.x; }
bool cmp2(node x, node y) { return x.x == y.x ? (x.y == y.y ? x.z < y.z : x.y < y.y) : x.x < y.x; }
bool cmp3(node x, node y) { return x.y > y.y; }
bool cmp4(node x, node y) { return x.y < y.y; }
int lowbit(int x) { return x & (-x); }
void add(int x, int dp, double f)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        if(tr1[i] < dp) { tr1[i] = dp, tr2[i] = f; }
        else if(tr1[i] == dp) { tr2[i] += f; }
    }
}
int qry1(int x) {
    int r = 0; for(int i = x; i; i -= lowbit(i)) up(r, tr1[i]); return r;
}
double qry2(int x, int dp) {
    double r = 0; for(int i = x; i; i -= lowbit(i)) if(tr1[i] == dp) r += tr2[i]; return r;
}
void del(int x) {
    for(int i = x; i <= n; i += lowbit(i)) tr1[i] = tr2[i] = 0;
}
void cdq(int l, int r, int type)
{
    if(l == r) return;
    int mid = (l + r) >> 1; cdq(l, mid, type);
    if(type == 1) {
        sort(a + l, a + mid + 1, cmp3); sort(a + mid + 1, a + r + 1, cmp3);
    }else {
        sort(a + l, a + mid + 1, cmp4); sort(a + mid + 1, a + r + 1, cmp4);
    }
    int j = l;
    for(int i = mid + 1; i <= r; i++)
    {
        if(type == 1) { 
            for(; a[j].y >= a[i].y && j <= mid; j++) add(a[j].z, a[j].dp, a[j].f);
        }else { 
            for(; a[j].y <= a[i].y && j <= mid; j++) add(a[j].z, a[j].dp, a[j].f);
        }
        int val = qry1(a[i].z) + 1;
        if(a[i].dp < val) { a[i].dp = val; a[i].f = qry2(a[i].z, val - 1); }
        else if(a[i].dp == val) { a[i].f += qry2(a[i].z, val - 1); }
    }
    for(int i = l; i < j; i++) del(a[i].z);
    if(type == 1) {
        sort(a + mid + 1, a + r + 1, cmp1);
    }else {
        sort(a + mid + 1, a + r + 1, cmp2);
    }
    cdq(mid + 1, r, type);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, x, y; i <= n; i++) { cin >> x >> y; a[i] = {x, y, i, 1, 1}; }
    sort(a + 1, a + 1 + n, cmp1); cdq(1, n, 1); int mx = 0;
    for(int i = 1; i <= n; i++)
    {
        dp1[a[i].z] = a[i].dp;
        f1[a[i].z] = a[i].f; up(mx, dp1[a[i].z]);
    }
    cout << mx << '\n' << fixed << setprecision(8);
    for(int i = 1; i <= n; i++) { a[i].z = n - a[i].z + 1; a[i].dp = 1; a[i].f = 1; }
    sort(a + 1, a + 1 + n, cmp2); cdq(1, n, 2); double sum = 0;
    for(int i = 1; i <= n; i++)
    {
        dp2[n - a[i].z + 1] = a[i].dp;
        f2[n - a[i].z + 1] = a[i].f;
        if(dp2[n - a[i].z + 1] == mx) sum += f2[n - a[i].z + 1]; 
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(dp1[i] + dp2[i] != mx + 1) cout << 0 << " \n"[i == n];
        else cout << f1[i] * f2[i] / sum << " \n"[i == n];
    }
    return 0;
}