Link

这道题不要去darkbzoj上交,估计是当时没加SPJ导致你无论如何都过不去

Sol

导弹拦截大家都会

现在已经给你了导弹来的顺序,我们把这个顺序记做 t_i

我们先来解决第一问,也就是最多能拦截的导弹数量。我们设f_i表示以i为最后一枚拦截的导弹前面最多能拦多少枚,记g_i为达到f_i的方案数。那么O(n^2)的转移非常好写。在f_i转移的时候看一下答案更新的情况,如果f_i不变就乘法原理乘一下g_i, 否则变成0

注意到f_i只能是从i的左边转移过来,看看能不能用cdq分治解决这个问题。现在t_i已经被确定,也就是说,已经有一维被确定,把h_i当做第二维,每次cdq的时候查一查左边的h比右边的h大的时候,就会产生贡献。更加具体的,我们把f_ig_i插到线段树中,当要更新答案的时候就可以从线段树中取出最大的f_ig_i更新当前的结果。

就这么写还是有锅,因为一种方案的方案数应该是以它开头和以它结尾的方案数的成绩。所以我们把三维全部逆过来,然后再做一遍cdq就可以了。

此外,注意方案数相加相乘会爆long long,用double存就可以了

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 5e4 + 5;

int n;
int f1[SIZE], f2[SIZE];
double g1[SIZE], g2[SIZE], cpy[SIZE];

struct DF { 
    int t, h; double v;
} a[SIZE];

struct node {
    int l, r, mx; double cnt;
} tree[SIZE << 2];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void pushUp(int p) {
    tree[p].mx = std::max(tree[lson(p)].mx, tree[rson(p)].mx), tree[p].cnt = 0.00;
    if (tree[p].mx == tree[lson(p)].mx) tree[p].cnt += tree[lson(p)].cnt;
    if (tree[p].mx == tree[rson(p)].mx) tree[p].cnt += tree[rson(p)].cnt;
}

void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r, tree[p].cnt = 0.00;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson(p), l, mid); build(rson(p), mid + 1, r);
    pushUp(p);
}

void modify(int p, int pos, int f, double g) {
    if (tree[p].l == tree[p].r) {
        if (tree[p].mx < f) tree[p].mx = f, tree[p].cnt = 0.00;
        if (tree[p].mx == f) tree[p].cnt += g;
        return;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (pos <= mid) modify(lson(p), pos, f, g);
    else modify(rson(p), pos, f, g);
    pushUp(p);
}

pair < int, double > query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        pair < int, double > ans; ans.first = tree[p].mx, ans.second = tree[p].cnt;
        return ans;
    }
    int mid = (tree[p].l + tree[p].r) >> 1; pair < int, double > ansl, ansr, ans;
    if (l <= mid) ansl = query(lson(p), l, r);
    if (r > mid) ansr = query(rson(p), l, r);
    int mX = std::max(ansl.first, ansr.first); ans.first = mX, ans.second = 0.00;
    if (mX == ansl.first && l <= mid) ans.second += ansl.second;
    if (mX == ansr.first && r > mid) ans.second += ansr.second;
    return ans;
}

void clear(int p, int l, int r) {
    if (tree[p].mx == 0) return;
    tree[p].mx = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    clear(lson(p), l, mid), clear(rson(p), mid + 1, r); 
}

int cmp1(DF a, DF b) { return a.t < b.t; }
int cmp2(DF a, DF b) { return a.h == b.h ? a.t < b.t : a.h > b.h; }

void cdq1(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    std::sort(a + l, a + r + 1, cmp1);; cdq1(l, mid);
    std::sort(a + l, a + mid + 1, cmp2); std::sort(a + mid + 1, a + r + 1, cmp2);
    clear(1, 1, n); pair < int, double > ans;
    for (int i = l, j = mid + 1; j <= r; ++ j) {
        while (i <= mid && a[i].h >= a[j].h) {
            modify(1, a[i].v, f1[a[i].t], g1[a[i].t]);
            ++ i;
        }
        ans = query(1, a[j].v, n);
        if (ans.first == 0) continue;
        if (f1[a[j].t] < ans.first + 1) f1[a[j].t] = ans.first + 1, g1[a[j].t] = 0.00;
        if (f1[a[j].t] == ans.first + 1) g1[a[j].t] += ans.second;
    }
    cdq1(mid + 1, r);
}

void cdq2(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    std::sort(a + l, a + r + 1, cmp1); cdq2(l, mid);
    std::sort(a + l, a + mid + 1, cmp2); std::sort(a + mid + 1, a + r + 1, cmp2);
    clear(1, 1, n); pair < int, double > ans;
    for (int i = l, j = mid + 1; j <= r; ++ j) {
        while (i <= mid && a[i].h >= a[j].h) {
            modify(1, a[i].v, f2[a[i].t], g2[a[i].t]);
            ++ i;
        }
        ans = query(1, a[j].v, n);
        if (ans.first == 0) continue;
        if (f2[a[j].t] < ans.first + 1) f2[a[j].t] = ans.first + 1, g2[a[j].t] = 0.00;
        if (f2[a[j].t] == ans.first + 1) g2[a[j].t] += ans.second;
    }
    cdq2(mid + 1, r);
}

signed main() {
    n = read(); int mxH = 0, V = 0;
    for (int i = 1; i <= n; ++ i) {
        a[i].t = i, a[i].h = read(), a[i].v = cpy[i] = (double) read();
        mxH = std::max(mxH, a[i].h);
    }
    std::sort(cpy + 1, cpy + n + 1);
    V = std::unique(cpy + 1, cpy + n + 1) - cpy - 1;
    for (int i = 1; i <= n; ++ i) {
        a[i].v = lower_bound(cpy + 1, cpy + V + 1, a[i].v) - cpy;
        f1[i] = f2[i] = 1, g1[i] = g2[i] = 1.000;
    }
    build(1, 1, n);
    std::sort(a + 1, a + n + 1, cmp1);
    cdq1(1, n);
    int res = 0; double tot = 0.00;
    for (int i = 1; i <= n; ++ i) res = std::max(res, f1[i]);
    for (int i = 1; i <= n; ++ i) {
        if (f1[i] == res) tot += g1[i];
    }
    printf("%lld\n", res);
    for (int i = 1; i <= n; ++ i) a[i].t = n - a[i].t + 1, a[i].h = mxH - a[i].h + 1, a[i].v = V - a[i].v + 1;
    std::sort(a + 1, a + n + 1, cmp1);
    clear(1, 1, n), cdq2(1, n);
    for (int i = 1; i <= n; ++ i) {
        if (f1[i] + f2[n - i + 1] - 1 != res) printf("%.6lf ", 0.0);
        else printf("%.6lf ", g1[i] * g2[n - i + 1] / tot);
    }
    puts("");
    return 0;
}

生存 关心