HYSBZ - 1067(降雨量)

題面：我們常常會說這樣的話：“X年是自Y年以來降雨量最多的”。它的含義是X年的降雨量不超過Y年，且對于任意

Y＜Z＜X，Z年的降雨量嚴格小于X年。例如2002，2003，2004和2005年的降雨量分别為4920，5901，2832和3890，

則可以說“2005年是自2003年以來最多的”，但不能說“2005年是自2002年以來最多的”由于有些年份的降雨量未

知，有的說法是可能正确也可以不正确的。

分析：RMQ查詢，不算難，但需要細心。設查詢的年份為 L 和 R （R>L），現在分析為true的情況，則

①：L，R降雨量已知；

②：R 的降雨量小于等于 L ;

③：L，R之間的年份的降雨量全部已知；

④：L，R之間已知的年份的降雨量都嚴格小于 L 和 R；

同時滿足上述4個條件才是true，

而maybe的情況分别是：

1）滿足①，②，④，但是不滿足③，即L和R之間年份不全部知道，但是知道的都滿足條件；

2）L 和 R 都未知；

3）L 未知，但是滿足L，R之間已知的年份的降雨量都嚴格小于R；

4）R 未知，但是滿足L，R之間已知的年份的降雨量都嚴格小于L；

那剩下的情況都隻能是false了。

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

const int N = 5*1e4+10;

int s[N],n,q;
int rmq[N][20];
int year[N];
void init()
{
    memset(rmq,0,sizeof(rmq));
    for(int i=0;i<n;i++) rmq[i][0]=s[i];
    for(int k=1;(1<<k)<=n;k++)
    for(int i=0;i+(1<<k)-1<=n;i++)
    {
        rmq[i][k]=max(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
    }
}

int query(int l,int r)
{
    if(l>r) return -1;
    int k=0;
    while((1<<k)<=r-l+1) k++;
    k--;
    int ans=max(rmq[l][k],rmq[r-(1<<k)+1][k]);
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)  scanf("%d%d",&year[i],&s[i]);
    init();
    scanf("%d",&q);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int L=lower_bound(year,year+n,l)-year;
        int R=lower_bound(year,year+n,r)-year;

        if(year[L]==l&&year[R]==r&&r-l==R-L&&s[L]>=s[R])  //所有條件已知
        {
            int st=query(L+1,R-1);
            if(st<s[R]) puts("true");
            else puts("false");
        }
        else if(year[L]==l&&year[R]==r&&r-l!=R-L&&s[L]>=s[R])
        {
            int st=query(L+1,R-1);
            if(st<s[R]) puts("maybe");
            else puts("false");
        }
        else if(year[L]!=l&&year[R]==r)  //左端點未知
        {
            int st=query(L,R-1);
            if(st<s[R]) puts("maybe");
            else puts("false");
        }
        else if(year[L]==l&&year[R]!=r)  //右端點未知
        {
            int st=query(L+1,R-1);
            if(st<s[L]) puts("maybe");
            else puts("false");
        }
        else if(year[L]!=l&&year[R]!=r) puts("maybe");
        else puts("false");
    }
}