Description

题目链接

Solution

虽说是个梗,这题目还是挺烦人的...

首先将所有年份离散化。注意 maybe 的情况是需要特殊处理的,所以我们离散化时如果两个年份之间相差不止 $1$ 年就新增一个年份,权值 $v_i$ 设为 $\infty$。

接下来用 ST 表维护两个最大值,一个是考虑无穷的最大值,一个是不考虑无穷的最大值,分别设为 $f$ 和 $g$。

转换一下题目的要求:$v_l \ge v_r > v_i (i \in (l, r))$。

然后处理询问,这里需要分类讨论:

  • $v_l = v_r = \infty$:答案为 maybe。
  • $v_l = \infty$:如果 $g(l + 1, r - 1) \ge v_r$ 则为 false,否则为 maybe。
  • $v_r = \infty$:如果 $v_l \le g(l + l, r - 1)$ 则为 false,否则为 maybe。
  • $v_l, v_r$ 都已知:如果 $v_l < v_r$ 或者 $g(l + 1, r - 1) \ge v_r$,答案为 false,否则如果 $f(l + 1, r - 1) \ge v_r$,答案为 maybe,否则为 true。

由于 $l + 1$ 可能大于 $r - 1$,还需要特判 $l + 1 = r$ 的情况。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Query {
    int l, r;
} b[10010];

int f[200010][20], g[200010][20];
int y[50010], A[200010], w[200010], v1[200010], v2[200010], lg[200010], r[50010];
int n, m, len;

int queryMax1(int l, int r) {
    int x = lg[r - l + 1];
    return std::max(f[l][x], f[r - (1 << x) + 1][x]);
}

int queryMax2(int l, int r) {
    int x = lg[r - l + 1];
    return std::max(g[l][x], g[r - (1 << x) + 1][x]);
} 

int main() {
    read(n);
    for (int i = 2; i <= 200000; ++i)    lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)    read(y[i]), read(r[i]), A[++len] = y[i];
    read(m);
    for (int i = 1; i <= m; ++i)    read(b[i].l), read(b[i].r), A[++len] = b[i].l, A[++len] = b[i].r;
    std::sort(A + 1, A + len + 1);
    int l = len;
    for (int i = 1; i <= l; ++i)    A[++len] = A[i] + 1;
    std::sort(A + 1, A + len + 1);
    len = std::unique(A + 1, A + len + 1) - A - 1;
    for (int i = 1; i <= len; ++i)    v1[i] = 2e9, v2[i] = -2e9;
    for (int i = 1; i <= n; ++i)    y[i] = std::lower_bound(A + 1, A + len + 1, y[i]) - A;
    for (int i = 1; i <= n; ++i)    v1[y[i]] = v2[y[i]] = r[i];
    for (int i = 1; i <= m; ++i)    b[i].l = std::lower_bound(A + 1, A + len + 1, b[i].l) - A, b[i].r = std::lower_bound(A + 1, A + len + 1, b[i].r) - A;
    for (int i = 1; i <= len; ++i)    f[i][0] = v1[i], g[i][0] = v2[i];
    for (int j = 1; j <= 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= len; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = std::max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (v1[b[i].r] == 2e9 && v1[b[i].l] == 2e9) {
            puts("maybe");
            continue;
        }
        if (b[i].l + 1 == b[i].r) {
            if (v1[b[i].r] == 2e9 || v1[b[i].l] == 2e9) {
                puts("maybe");
            } else if (v1[b[i].r] <= v1[b[i].l]) {
                puts("true");
            } else {
                puts("false");
            }
            continue;
        }
        if (v1[b[i].l] == 2e9) {
            if (queryMax2(b[i].l + 1, b[i].r - 1) >= v1[b[i].r]) {
                puts("false");
            } else {
                puts("maybe");
            }
        } else {
            if (v1[b[i].r] == 2e9) {
                if (v1[b[i].l] <= queryMax2(b[i].l + 1, b[i].r - 1)) {
                    puts("false");
                } else {
                    puts("maybe");
                }
            } else {
                if (v1[b[i].l] < v1[b[i].r] || queryMax2(b[i].l + 1, b[i].r - 1) >= v1[b[i].r]) {
                    puts("false");
                } else if (queryMax1(b[i].l + 1, b[i].r - 1) >= v1[b[i].r]) {
                    puts("maybe");
                } else {
                    puts("true");
                }
            }
        }
    }
    return 0;
}
Last modification:September 5th, 2021 at 01:18 am