Solution -「SDOI2011」拦截导弹

Sol.

题目要求一个数对序列的二维最长下降子序列，我们称其为 Q。并求出每一个元素分别在可能的 Q 中出现了多少次。

直接 Dp，时间复杂度 \(O(n^2)\) 不行。考虑 CDQ 分治优化 Dp。即我们每次在分治时，先递归左半部分，在根据左半部分转移右半部分，最后递归右半部分。嗯。很有道理。

CDQ 维护两组 pair 值，first 统一表示长度，second 统一表示方案数，而 \(dp_{i, 0}\) 和 \(dp_{i, 1}\) 分别指以 \(i\) 结尾和以 \(i\) 开头的 Q 的信息，因为是二维信息再加一位时间，所以大体框架类似三维偏序。

只不过在 CDQ 中的分治归并排序必须排但又不完全排，即要先拎出来放进备份，然后在备份上操作，这样就可以让当前还未内部转移的右半部分保持顺序不动，然后在后面在递归进行内部转移。而备份上的操作又可以把左半部分到右半部分的外部转移做了。嗯。可以打了。

补充一下，得出 \(dp_{i, 0}\) 和 \(dp_{i, 1}\) 需要正反跑两次 CDQ，时间复杂度 \(O(n\log^2n)\)。

Code.

#include <cstdio>

#include <algorithm>

using namespace std;

int Abs (int x) { return x < 0 ? -x : x; }

int Max (int x, int y) { return x > y ? x : y; }

int Min (int x, int y) { return x < y ? x : y; }

int Read () {

    int x = 0, k = 1;

    char s = getchar();

    while (s < '0' || s > '9') {

        if(s == '-')

            k = -1;

        s = getchar ();

    }

    while ('0' <= s && s <= '9')

        x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();

    return x * k;

}

void Write (int x) {

    if(x < 0)

        x = -x, putchar ('-');

    if(x > 9)

        Write (x / 10);

    putchar (x % 10 + '0');

}

void Print (int x, char s) { Write (x), putchar (s); }

const int MAXN = 5e4 + 5;

bool Type;

// 把两个 CDQ Rua 到一起又要在一些细节有所区分，所以开个 bool。

int Num[MAXN], Len;

#define pid pair<int, double>

// long long 是假的，这道题中间过程不止 long long。

// 而 double 钟爱存储大小，原因因此舍弃一些精度，而这刚好符合我们的需求。

pid Dp[MAXN][2], BIT[MAXN][2];

pid operator + (pid a, pid b) { // pair 的加法重载。

    return make_pair (a.first + b.first, a.second + b.second);

}

pid Max_Pair (pid x, pid y) { // 便于方程转移的手写 Max。

    if (x.first != y.first)

        return x.first > y.first ? x : y;

    return make_pair (x.first, x.second + y.second);

}

int Low_Bit (int x) { return x & -x; }

void Clear (int k) {

    if (!Type) {

        for (int i = k; i; i -= Low_Bit(i))

            BIT[i][0] = make_pair (0, 0);

    }

    else {

        for (int i = k; i <= Len; i += Low_Bit(i))

            BIT[i][1] = make_pair (0, 0);

    }

}

void Update (int k, pid x) {

    if (!Type) {

        for (int i = k; i; i -= Low_Bit(i))

            BIT[i][0] = Max_Pair (BIT[i][0], x);

    }

    else {

        for (int i = k; i <= Len; i += Low_Bit(i))

            BIT[i][1] = Max_Pair (BIT[i][1], x);

    }

}

pid Query (int k) {

    pid Res = make_pair (0, 0);

    if (!Type) {

        for (int i = k; i <= Len; i += Low_Bit(i))

            Res = Max_Pair (Res, BIT[i][0]);

        return Res;

    }

    else {

        for (int i = k; i; i -= Low_Bit(i))

            Res = Max_Pair (Res, BIT[i][1]);

        return Res;

    }

}

// 将两颗 BIT Rua 在一起，用 Type 使得两个 CDQ 维护的信息刚好反过来。

struct Node {

    int h, v, Id;

    Node () {}

    Node (int H, int V, int I) {

        h = H, v = V, Id = I;

    }

} q[MAXN], Tmp[MAXN];

// Tmp 即我们操作的备份。

bool Check (int x, int y) { return !Type ? x >= y : x <= y; }

bool Cmp (Node x, Node y) { return !Type ? x.h > y.h : x.h < y.h; }

// 两种不同的排序方式，因偏序实现不同因人而异。用 Type 控制相反。

void CDQ (int l, int r) {

    if (l == r)

        return ;

    int Mid = (l + r) >> 1;

    CDQ (l, Mid);

    for (int i = l; i <= r; i++)

        Tmp[i] = q[i];

    sort (Tmp + l, Tmp + Mid + 1, Cmp);

    sort (Tmp + Mid + 1, Tmp + r + 1, Cmp);

    // 排序，又不完全排序。注意这里是在备份上操作，以完成偏序。

    for (int i = l, j = Mid + 1; j <= r; j++) {

        while (i <= Mid && Check (Tmp[i].h, Tmp[j].h))

            Update (Tmp[i].v, Dp[Tmp[i].Id][Type]), i++ /*, printf ("%d %d\n", Type, i)*/ ;  // 遍历新的可能对当前 j 产生转移贡献的 i。

        Dp[Tmp[j].Id][Type] = Max_Pair (Dp[Tmp[j].Id][Type], Query (Tmp[j].v) + make_pair (1, 0));

        // 转移方程。Type 控反。

        // printf ("%d %d %d %d\n", Type, Tmp[j].Id, Dp[Tmp[j].Id][Type].first, (Query (Tmp[j].v) + make_pair (1, 0)).first);

    }

    for (int i = l; i <= Mid; i++)

        Clear (Tmp[i].v);

    // 记得将 BIT 清空，不影响以后的转移。

    CDQ (Mid + 1, r);

}

/*

133 行，曾出现了一个 ub。

Update (Tmp[i].v, Dp[Tmp[i].Id][Type]), i++;

不等价于

Update (Tmp[i].v, Dp[Tmp[i++].Id][Type]);

原因或许是函数传参从右到左。

*/

int main () {

    int n = Read ();

    for (int i = 1; i <= n; i++) {

        q[i].h = Read (), q[i].v = Read (), q[i].Id = i;

        Num[i] = q[i].v;

    }

    sort (Num + 1, Num + n + 1);

    Len = unique (Num + 1, Num + n + 1) - Num - 1;

    for (int i = 1; i <= n; i++)

        q[i].v = lower_bound (Num + 1, Num + Len + 1, q[i].v) - Num;

   	// BIT 和值域有关，所以离散化。

    for (int i = 1; i <= n; i++)

        Dp[i][0] = Dp[i][1] = make_pair (1, 1);

   	// Dp 初值，即当前 Q 只有 i 一个元素。

    CDQ (1, n);

    reverse (q + 1, q + n + 1);

    Type = 1, CDQ (1, n);

    pid Ans = make_pair (0, 0);

    for (int i = 1; i <= n; i++)

        Ans = Max_Pair (Ans, Dp[i][0]);

    Print (Ans.first, '\n');

    // for (int i = 1; i <= n; i++)

    //     printf ("%d %f %d %f\n", Dp[i][0].first, Dp[i][0].second, Dp[i][1].first, Dp[i][1].second);

    for (int i = 1; i <= n; i++)

        if (Dp[i][0].first + Dp[i][1].first - 1 == Ans.first)

        // 判断当前 i 是否被至少一个 Q 所包含

            printf ("%.5f ", Dp[i][0].second * Dp[i][1].second / Ans.second);

        else

            printf ("0.00000 ");

    return 0;

}

/*

180 行也曾有一个未发现原因的 ub。

printf ("0.00000 ");

不等价于

printf ("%.5f ", 0);

*/

巴特西

Solution -「SDOI2011」拦截导弹

Sol.

Code.

最新文章

热门文章