https://blog.csdn.net/tenkuo/article/details/154677859

C30 线段树 P2471 [SCOI2007] 降雨量

#include <bits/stdc++.h>
using namespace std;
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
typedef long long LL;
const int N = 1e5 + 10;
struct trnode { int l, r, mx; } tr[N * 4];
int Y[N], a[N];

void pushup(int p) { tr[p].mx = max(tr[lc(p)].mx, tr[rc(p)].mx); }

void bt(int p, int l, int r) {
    tr[p] = trnode{ l, r, 0 };
    if (l == r) { tr[p].mx = a[l]; return; }
    int m = (l + r) / 2;
    bt(lc(p), l, m);
    bt(rc(p), m + 1, r);
    pushup(p);
}

int query(int p, int l, int r) {
    if (r < tr[p].l || tr[p].r < l) return 0;
    if (l <= tr[p].l && tr[p].r <= r) return tr[p].mx;
    return max(query(lc(p), l, r), query(rc(p), l, r));
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &Y[i], &a[i]);
    bt(1, 1, n);
    int m; scanf("%d", &m);
    while (m--) {
        int y, x; scanf("%d%d", &y, &x);
        int l = lower_bound(Y + 1, Y + n + 1, y) - Y;
        int r = lower_bound(Y + 1, Y + n + 1, x) - Y;
        int bl = (Y[l] == y);
        int br = (Y[r] == x);
        if (!bl) l--;
        int mx = query(1, l + 1, r - 1);
        
        if (bl && br && x - y == r - l && a[r] <= a[l] && a[r] > mx) printf("True\n");
        else if ((bl && mx >= a[l]) || (br && mx >= a[r]) || (bl && br && a[r] > a[l])) printf("False\n");
        else printf("maybe\n");
    }
    return 0;
}