仅用于(也专用于)写题解,其他的去 kewth.github.io 玩啊~~

题解 AT2383 【Mr.Aoki Incubator】

2019-12-16 22:20:30


足够长的时间后,点一定是按速度排序的,不妨假定 v 升序。
考虑点 i 被染色后有哪些点会被染到,事实上染到的一定是一段区间 [l, r] ,
l 是最小的满足 x[l] >= x[i] 的下标,
r 是最大的满足 x[r] <= x[i] 的下标。

原因:
i 最开始在 l 左边 (x[l] >= x[i]),最后一定会在 l 右边 (v[l] <= v[i]) ,
可以反证最后在 [l, i] 区间内的点都会被经过,
对于 r 同理。

求出了所有点的 [l, r] 后,问题转换为选择若干 [l, r] 使得它们的并为 [1, n] 。
根据定义不难发现 l, r 都 随 x[i] 的增大单调不降。
那么再将点按 x 升序,此时的 l, r 也就都是升序的了。

DP 设 f[i] 表示用前 i 个区间,钦定第 i 个区间必选,覆盖 [1, r[i]] 的方案数。
对于所有满足 r[j] >= l[i] - 1 且 j < i 的 j 都可以从 f[j] 转移到 f[i] 。
而 r 是升序的,这意味着只要 f[j] 能转移到 f[i] ,f[j + 1] 就能转移到 f[i] ,
换言之,f[i] 的转移是一段区间 [L, i - 1] ,其中 L 是满足条件的最小 j 。
而同时 l 也是升序的,这意味着 L 也是升序的,dp 的过程中维护这个 L 即可。
区间转移用前缀和优化即可做到 $O(1)$ 。

实现上并不需要反复排序,只需要将 x 离散化后就可以替代第二次排序,
并且 x 离散化后求 l, r 相当于求一类前缀后缀最值。
总复杂度 $O(nlogn)$ ,瓶颈在于排序和离散化。

参考实现:

#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef std::pair<int, int> Par;

struct {
    inline operator int () { int x; return scanf("%d", &x), x; }
    inline operator ll () { ll x; return scanf("%lld", &x), x; }
    template<class T> inline void operator () (T &x) { x = *this; }
    template<class T, class ...A> inline void operator () (T &x, A &...a)
    { x = *this; this -> operator ()(a...); }
} read;

const int maxn = 200005, mod = 1000000007;
int l[maxn], r[maxn];
int p[maxn];
int tmp[maxn];
Par pr[maxn];
ll f[maxn], s[maxn];

int main() {
    int n = read;

    for(int i = 1; i <= n; i ++)
        read(pr[i].second, pr[i].first);
    std::sort(pr + 1, pr + n + 1);

    for(int i = 1; i <= n; i ++)
        tmp[i] = pr[i].second;
    std::sort(tmp + 1, tmp + n + 1);

    for(int i = 1; i <= n; i ++) {
        pr[i].second = int(std::lower_bound(tmp + 1, tmp + n + 1, pr[i].second) - tmp);
        p[pr[i].second] = i;
    }

    for(int i = 1; i <= n; i ++)
        r[i] = std::max(r[i - 1], p[i]);
    l[n] = p[n];
    for(int i = n - 1; i; i --)
        l[i] = std::min(l[i + 1], p[i]);

    int L = 0;
    f[0] = s[0] = 1;

    for(int i = 1; i <= n; i ++) {
        while(r[L] < l[i] - 1)
            ++ L;
        f[i] = (s[i - 1] - s[L - 1] + mod) % mod;
        s[i] = (s[i - 1] + f[i]) % mod;
    }

    while(r[L] < n)
        ++ L;
    printf("%lld\n", (s[n] - s[L - 1] + mod) % mod);
}