洛谷P2471 [SCOI2007] 降雨量 题解

题目链接：P2471 [SCOI2007] 降雨量

题意：

我们常常会说这样的话：“\(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\) 年以来降雨量最多的。”这句话是“必真”、“必假”还是“有可能”。

输出格式：

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

数据范围：

\(100 \%\) 的数据满足：\(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\)。

线段树板子+简单二分+大分讨，如下：

这个奇妙的 1e9 是假设题目最大降雨量不超过 1e9，不过测试数据里并没有体现出，果然啥b题。

时间复杂度 \(\mathcal{O}((n+m)\log n)\)

代码：（注意特判 \(Y\) 不小于 \(X\) 的询问）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n,m,date[N], val[N], mx[N * 4];
void push_up(int at) { up(mx[at] = mx[ls(at)], mx[rs(at)]); }
void build(int l,int r,int at)
{
    if(l == r) { return mx[at] = val[l], void(0); }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(mid+1,r,rs(at)); push_up(at);
}
int query(int nl, int nr,int l = 1,int r = n,int at = 1)
{
    if(nl > nr) return 0;
    if(nl <= l && r <= nr) { return mx[at]; }
    int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at)); 
    return max(query(nl,nr,l,mid,ls(at)), query(nl,nr,mid+1,r,rs(at)));  
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) { cin >> date[i] >> val[i]; }
    build(1,n,1); cin >> m;
    for(int i = 1,a,b; i <= m; i++)
    {
        cin >> a >> b; if(a > b) { cout << "false\n"; continue; }
        int l = lower_bound(date + 1, date + 1 + n, a) - date;
        int r = lower_bound(date + 1, date + 1 + n, b) - date;
        // cout << "l = " << l << ", r = " << r << '\n';
        // cout << date[l] << ' ' << val[l] << ", " << date[r] << ' ' << val[r] << '\n';
        if(date[l] != a)
        {
            if(query(l, r - 1) == INF) { cout << "false\n"; continue; }
            if(date[r] != b) { cout << "maybe\n"; continue;}
            else { cout << (val[r] > query(l, r - 1) ? "maybe\n" : "false\n"); continue; }
        }else
        {
            if(date[r] != b)
            {
                if(query(l + 1, r - 1) == INF) { cout << "false\n"; continue; }
                cout << (val[l] > query(l + 1, r - 1) ? "maybe\n" : "false\n"); continue;
            }else
            {
                if(val[l] < val[r]) { cout << "false\n"; continue; }
                if(r - l + 1 == b - a + 1) {
                    cout << (query(l + 1,r - 1) < val[r] ? "true\n" : "false\n"); continue; 
                }else { cout << (query(l + 1,r - 1) < val[r] ? "maybe\n" : "false\n"); continue; }
            }
        }
        cout << "真nm离谱了这个分讨\n";
    }
    return 0;
}