BZOJ_1067_[SCOI2007]降雨量_ST表

Description

　　我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，
则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知，有的说法是可能正确也可以不正确的。

Input

　　输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小
到大排列，即yi＜yi+1。下一行包含一个正整数m，为询问的次数。以下m行每行包含两个数Y和X，即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

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

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

用一个ST表维护区间最大值。然后每次lower_bound一下查询的x，y。

然后各种分类讨论就做完了。

我的分类比较麻烦吧。。。把x，y的存在性的可能都拿出来然后一个一个判断。

不过还是没有1A，原因是每次确定的x的后继pre和y的后继nxt可能出现pre>nxt这种情况，判掉就好啦。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

#define C1 puts("true")

#define C2 puts("false")

#define C3 puts("maybe")

#define N 50050

int a[N],b[N],n,m,f[21][N],Lg[N];

int get_max(int l,int r) {

    int len=Lg[r-l+1];

    return max(f[len][l],f[len][r-(1<<len)+1]);

}

int main() {

    scanf("%d",&n);

    int i,x,y;

    for(Lg[0]=-1,i=1;i<=n;i++) {

        scanf("%d%d",&a[i],&b[i]); f[0][i]=b[i]; Lg[i]=Lg[i>>1]+1;

    }

    int j;

    for(i=1;(1<<i)<=n;i++) {

        for(j=1;j+(1<<i)-1<=n;j++) {

            f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);

        }

    }

    scanf("%d",&m);

    while(m--) {

        scanf("%d%d",&x,&y);

        if(x==y) {

            C1; continue;

        }

        if(x>y) {

            C2; continue;

        }

        int tx=1,ty=1,nxt,pre;

        if(x>=a[n]||y<=a[1]) {

            C3; continue;

        }

        int kx=lower_bound(a+1,a+n+1,x)-a,ky=lower_bound(a+1,a+n+1,y)-a;

        if(a[kx]==x) nxt=kx+1;

        else nxt=kx,tx=0;

        if(a[ky]==y) pre=ky-1;

        else pre=ky-1,ty=0;

        int maxx=0;

        if(nxt<=pre) maxx=get_max(nxt,pre);

        if(!tx&&!ty) C3;

        else if(tx&&!ty) {

            if(maxx>=b[kx]) C2;

            else C3;

        }else if(!tx&&ty) {

            if(maxx>=b[ky]) C2;

            else C3;

        }else {

            if(maxx>=b[ky]||b[ky]>b[kx]) C2;

            else if(a[ky]-a[kx]==ky-kx) C1;

            else C3;

        }

    }

}