题意分析

题目要求判断一系列关于降雨量的陈述："X年是Y年以来降雨量最多的年份"的正确性。陈述可能有三种结果： true：陈述确定成立 maybe：陈述可能成立 false：陈述确定不成立 true条件： $Y$和$X$年份的降雨量均已知 $X$年降雨量 $≤ Y$年降雨量 区间$(Y, X)$内所有年份降雨量均已知且严格小于$X$年降雨量

maybe条件： 存在一种为未知年份分配降雨量的方式使陈述成立

false条件： 已知信息已经违反陈述条件

解题思路

使用两个数组分别存储年份和降雨量,题目中以确保数据有序。构建稀疏表，方便高效查询区间最高降水量。使用二分法具体查找年份信息。

标程

#include <bits/stdc++.h>
using namespace std;

const long long INF = 2000000000000000000LL;
const int MAXN = 50000;
const int LOG = 16;

long long rains[MAXN];
long long years[MAXN];
long long st[MAXN][LOG + 1];
int log2table[MAXN + 1];

void init_log() {
    log2table[1] = 0;
    for (int i = 2; i <= MAXN; i++) {
        log2table[i] = log2table[i / 2] + 1;
    }
}

void build_st(int n) {
    if (n <= 0) return;

    for (int i = 0; i < n; i++) {
        st[i][0] = rains[i];
    }
    for (int j = 1; j <= LOG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

long long query_st(int l, int r) {
    if (l > r) return -INF;
    int len = r - l + 1;
    if (len <= 0) return -INF;  // 确保长度有效
    
    int j = log2table[len];
    int right_index = r - (1 << j) + 1;
    // 确保索引在有效范围内
    if (right_index < l) right_index = l;
    return max(st[l][j], st[right_index][j]);
}

int main() {
    init_log();
    int n, m;
    int test_case = 0;
    while (scanf("%d", &n) == 1) {
        if (n == 0) {
            scanf("%d", &m);
            if (m == 0) {
                break;
            }
            if (test_case > 0) {
                printf("\n");
            }
            test_case++;
            for (int i = 0; i < m; i++) {
                long long Y, X;
                scanf("%lld %lld", &Y, &X);
                printf("maybe\n");
            }
            continue;
        }

        for (int i = 0; i < n; i++) {
            scanf("%lld %lld", &years[i], &rains[i]);
        }

        if (n > 0) {  // 确保n>0时才构建ST表
            build_st(n);
        }
        
        scanf("%d", &m);

        if (test_case > 0) {
            printf("\n");
        }
        test_case++;

        for (int i = 0; i < m; i++) {
            long long Y, X;
            scanf("%lld %lld", &Y, &X);

            int L_index = lower_bound(years, years + n, Y) - years;
            int R_index = upper_bound(years, years + n, X) - years;

            // 验证索引范围
            bool hasY = (L_index >= 0 && L_index < n && years[L_index] == Y);
            bool hasX = (R_index > 0 && R_index - 1 < n && years[R_index - 1] == X);
            int cnt = R_index - L_index;

            long long mid_max = -INF;
            int start = L_index;
            if (hasY) start++;
            int end = R_index - 1;
            if (hasX) end--;

            // 严格边界检查
            if (start <= end && start >= 0 && end < n) {
                mid_max = query_st(start, end);
            }

            long long num_years = X - Y + 1;

            if (hasY && hasX) {
                if (rains[L_index] < rains[R_index - 1]) {
                    printf("false\n");
                } else {
                    if (mid_max >= rains[R_index - 1]) {
                        printf("false\n");
                    } else {
                        if (num_years == (long long)cnt) {
                            printf("true\n");
                        } else {
                            printf("maybe\n");
                        }
                    }
                }
            } else if (hasX) {
                if (mid_max >= rains[R_index - 1]) {
                    printf("false\n");
                } else {
                    printf("maybe\n");
                }
            } else if (hasY) {
                if (mid_max >= rains[L_index]) {
                    printf("false\n");
                } else {
                    printf("maybe\n");
                }
            } else {
                printf("maybe\n");
            }
        }
    }
    return 0;
}