P2471 降雨量

题目描述

我们常常会说这样的话：“$X$ 年是自 $Y$ 年以来降雨量最多的”。它的含义是 $X$ 年的降雨量不超过 $Y$ 年，且对于任意 $Y<Z<X$，$Z$ 年的降雨量严格小于 $X$ 年。例如 2002、2003、2004 和 2005 年的降雨量分别为 $4920$、$5901$、$2832$ 和 $3890$，则可以说“2005 年是自 2003 年以来最多的”，但不能说“2005 年是自 2002 年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。

输入格式

输入仅一行包含一个正整数 $n$，为已知的数据。以下 $n$ 行每行两个整数 $y_i$ 和 $r_i$，为年份和降雨量，按照年份从小到大排列，即 $y_i<y_{i+1}$。下一行包含一个正整数 $m$，为询问的次数。以下 $m$ 行每行包含两个数 $Y$ 和 $X$，即询问“$X$ 年是自 $Y$ 年以来降雨量最多的。”这句话是“必真”、“必假”还是“有可能”。

$1\le n\le 50000$，$1\le m\le 10000$，$-{10}^9\le y_i\le {10}^9$，$1\le r_i\le {10}^9$，$-{10}^9\le X,Y\le {10}^9$。

数据保证 $Y<X$。

输出格式

对于每一个询问，输出 true、false 或者 maybe。

Solution

线段树/ST 表

这个题只会用到线段树的区间查询最大值。

主要是条件判断的繁琐

从易到难：false, maybe, true

分类讨论：

• true：两边端点都存在，$[l,r]$ 中左端点最大，右端点严格小于左端点，中间的所有数严格小于右端点，$[l,r]$ 区间是连续的
• false：
  • 左端点存在：$[l+1,r-1]$ 区间端点的最大值比左端点大
  • 右端点存在：$[l+1,r-1]$ 区间端点的最大值比右端点大
  • 两边端点都存在，右端点比左端点大
• maybe：不是上面两种情况则成立

#define lc u<<1
#define rc u<<1|1
int year[100010], rain[100010], yl, yr;
bool bl, br;
struct Tree { //线段树
    ll l, r, max;
}tr[400010];
void pushup(ll u) { //上传
    tr[u].max = max(tr[lc].max, tr[rc].max);
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,rain[l]};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;
    ll m = tr[u].l + tr[u].r >> 1;
    ll ans = -1;
    if (l <= m) ans = max(ans, query(lc, l, r));
    if (r > m) ans = max(ans, query(rc, l, r));
    return ans;
}
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        int y, x;cin >> y >> x;year[i] = y;rain[i] = x;
    }
    build(1, 1, n);
    int m;cin >> m;
    while (m--) {
        int y, x;cin >> y >> x;
        yl = lower_bound(year + 1, year + 1 + n, y) - year;
        yr = lower_bound(year + 1, year + 1 + n, x) - year;
        bl = year[yl] == y;
        br = year[yr] == x;
        if (!bl)yl--;
        int maxx = query(1, yl + 1, yr - 1);
        if (bl && br && x - y == yr - yl && rain[yr] <= rain[yl] && rain[yr] > maxx) {
            cout << "true\n";
        } else if ((bl && maxx >= rain[yl]) || (br && maxx >= rain[yr]) || (bl && br && rain[yr] > rain[yl])) {
            cout << "false\n";
        } else {
            cout << "maybe\n";
        }
    }
}