bzoj1067

题意：

给你下雨量，让你判断每一句话是否正确

题解：

线段树

用来维护判断

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=;

struct seg

{

    int max;

}tree[N];

int n,m,x[N],y[N],sum[N];

void build(int rt,int L,int R)

{

    if (L==R)

     {

        tree[rt].max=y[L];

        return;

     }

    int mid=(L+R)>>;

    build(rt<<,L,mid);

    build((rt<<)+,mid+,R);

    tree[rt].max=max(tree[rt<<].max,tree[(rt<<)+].max);

}

int query(int rt,int L,int R,int QL,int QR)

{

    if (QL>R||QR<L) return -2e9;

    if (QL<=L&&QR>=R) return tree[rt].max;

    int mid=(L+R)>>;

    return max(query(rt<<,L,mid,QL,QR),

    query((rt<<)+,mid+,R,QL,QR));

}

int find(int X)

{

    int L=,R=n,mid;

    while (L<=R)

     {

        mid=(L+R)>>;

        if (x[mid]==X) return mid;

        if (x[mid]>X) R=mid-;

        if (x[mid]<X) L=mid+;

     }

    return -;

}

int find_2(int X)

{

    int L=,R=n,mid,res;

    while (L<=R)

     {

        mid=(L+R)>>;

        if (x[mid]>X) res=mid,R=mid-;

        else L=mid+;

     }

    return res;

}

int find_3(int X)

{

    int L=,R=n,mid,res;

    while (L<=R)

     {

        mid=(L+R)>>;

        if (x[mid]<X) res=mid,L=mid+;

        else R=mid-;

     }

    return res;

}

int main()

{

    scanf("%d",&n);

    for (int i=;i<=n;i++) scanf("%d%d",&x[i],&y[i]);

    build(,,n);

    scanf("%d",&m);

    for (int i=,x1,x2,bh1,bh2;i<=m;i++)

     {

        scanf("%d%d",&x1,&x2);

        if (!(x1<x2))

         {

            puts("false");

            continue;

         }

        bh1=find(x1),bh2=find(x2);

        if (bh1==- && bh2==-)

         {

            puts("maybe");

            continue;

          }

        if (bh2==-)

         {

            bh2=find_3(x2);

            if (bh1+>bh2||query(,,n,bh1+,bh2)<y[bh1])

             puts("maybe");

            else puts("false");

            continue;

         }

        if (bh1==-)

         {

            bh1=find_2(x1);

            if (bh1>bh2-||query(,,n,bh1,bh2-)<y[bh2])puts("maybe");

            else puts("false");

            continue;

         }

        if (!(y[bh1]>=y[bh2]))

         {

            puts("false");

            continue;

         }

        if (bh1+>bh2-||query(,,n,bh1+,bh2-)<y[bh2])

        if (x2-x1==bh2-bh1)puts("true");

        else puts("maybe");

        else puts("false");

     }

    return ;

}