P2471 降雨量
题目描述
我们常常会说这样的话:“
输入格式
输入仅一行包含一个正整数
数据保证
输出格式
对于每一个询问,输出 true
、false
或者 maybe
。
Solution
线段树/ST 表
这个题只会用到线段树的区间查询最大值。
主要是条件判断的繁琐
从易到难:false
, maybe
, true
分类讨论:
true
:两边端点都存在,中左端点最大,右端点严格小于左端点,中间的所有数严格小于右端点, 区间是连续的 false
:- 左端点存在:
区间端点的最大值比左端点大 - 右端点存在:
区间端点的最大值比右端点大 - 两边端点都存在,右端点比左端点大
- 左端点存在:
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";
}
}
}