欢迎访问~原文出处——

---

---

题意概括

    给定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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          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) 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
           
            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[fb].y) puts("false"); else if (xb-xa!=fb-fa) puts("maybe"); else puts("true"); } return 0;}