BZOJ1067 [SCOI2007]降雨量 线段树

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

---

题目传送门 - BZOJ1067

---

题意概括

    给定n组整数对（Xi,Yi），当Xi<Xj且Yi>=Yj时，如果对于任意的Xk，有Xi<Xk<Xj， Yk严格小于Yj，则称Xi是Xi到Xj中最牛的点。例如4个整数对（2002，4920），（2003，5901），（2004，2832），（2005，3890）,则可以说“2003”是2003至2005中最牛的点，但不能说是2002至2005中最牛的点。由于有些X坐标是未知的，有的说法是可能正确也可能不正确。

---

题解

　　这题要分情况讨论；

　　情况特别多。

　　详见代码。

　　因为要查询，所以用一棵线段树来维护区间最值。

---

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=50000+5;
int n,m,t[N*4];
struct Point{
    int x,y;
}P[N];
void build(int rt,int le,int ri){
    if (le==ri){
        t[rt]=P[le].y;
        return;
    }
    int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
    build(ls,le,mid);
    build(rs,mid+1,ri);
    t[rt]=max(t[ls],t[rs]);
}
int findR(int x){
    int le=1,ri=n,mid,ans=0;
    while (le<=ri){
        mid=(le+ri)>>1;
        if (P[mid].x==x)
            return mid;
        if (P[mid].x<x)
            le=mid+1,ans=mid;
        if (P[mid].x>x)
            ri=mid-1;
    }
    return ans+1;
}
int query(int rt,int le,int ri,int xle,int xri){
    if (xle>xri)
        return -2147483646;
    if (ri<xle||le>xri)
        return -2147483646;
    if (xle<=le&&ri<=xri)
        return t[rt];
    int mid=(le+ri)>>1;
    return max(query(rt<<1,le,mid,xle,xri),query(rt<<1|1,mid+1,ri,xle,xri));
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&P[i].x,&P[i].y);
    build(1,1,n);
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        int xa,xb,fa,fb;
        scanf("%d%d",&xa,&xb);
        if (xa>=xb){
            puts("false");
            continue;
        }
        fa=findR(xa),fb=findR(xb);
        P[n+1].x=max(xa,xb)+1;
        if (xb!=P[fb].x){
            if (xa!=P[fa].x){
                puts("maybe");
                continue;
            }
            puts(query(1,1,n,fa+1,fb-1)<P[fa].y?"maybe":"false");
            continue;
        }
        if (xa!=P[fa].x){
            puts(query(1,1,n,fa,fb-1)<P[fb].y?"maybe":"false");
            continue;
        }
        if (P[fa].y<P[fb].y){
            puts("false");
            continue;
        }
        if (query(1,1,n,fa+1,fb-1)>=P[fb].y)
            puts("false");
        else if (xb-xa!=fb-fa)
            puts("maybe");
        else
            puts("true");
    }
    return 0;
}