P2471 降雨量

Dec 16, 2024 11:43 AM
Dec 17, 2024 4:34 AM

题目描述

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

输入格式

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

1n500001m10000109yi1091ri109109X,Y109

数据保证 Y<X

输出格式

对于每一个询问,输出 truefalse 或者 maybe

Solution

线段树/ST 表

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

主要是条件判断的繁琐

从易到难:false, maybe, true

分类讨论:

#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";
        }
    }
}