BZOJ-1067: [SCOI2007]降雨量（RMQ）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1067

略恶心的一道题。。。RMQ+分类分类分类。。。

代码：

203fb80e7bec54e7e9d0b063bb389b504fc26a8b.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std ;
 
#define MAXN 50010
#define inf 0x7fffffff
#define MAXV MAXN *4
 
struct node{
        int y , r ;
} a[ MAXN ];
 
struct Sgt{
        int Max[ MAXV ], N ;
        
        void Init(int _N , node *a ){
               N =1<<(int(log2( _N +1))+1);
               for(int i =0; i ++< _N ;) Max[ N + i ]= a[ i ].r ;
               for(int i = N -1; i ; i --) Max[ i ]=max( Max[ i <<1], Max[( i <<1)^1]);
        }
        
        int query(int l ,int r ){
               if( l > r )return- inf ;
               int i = N + l -1, j = N + r +1, rec =- inf ;
               for(;( i ^ j )!=1; i >>=1, j >>=1){
                       if(!( i &1)) rec =max( Max[ i ^1], rec );
                       if( j &1) rec =max( rec , Max[ j ^1]);
               }
               return rec ;
        }
        
} sgt ;
 
int n , m ;
 
int Searchl(int x ){
        if( a[1].y >= x )return 1;
        if( a[ n ].y <= x )return n ;
        int l =1, r = n ;
        while( r - l >1){
               int mid =( l + r )>>1;
               if( a[ mid ].y == x )return mid ;
               if( a[ mid ].y < x ) l = mid ;else r = mid ;
        }
        return r ;
}
 
int Searchr(int x ){
        if( a[1].y >= x )return 1;
        if( a[ n ].y <= x )return n ;
        int l =1, r = n ;
        while( r - l >1){
               int mid =( l + r )>>1;
               if( a[ mid ].y == x )return mid ;
               if( a[ mid ].y < x ) l = mid ;else r = mid ;
        }
        return l ;
}
 
int main(  ){
        scanf("%d",&n );
        for(int i =0; i ++< n ;)scanf("%d%d",&a[ i ].y ,&a[ i ].r );
        sgt.Init( n , a );
        scanf("%d",&m );
        while( m --){
               int x , y ;scanf("%d%d",&x ,&y );
               int L =Searchl( x ), R =Searchr( y );
               int X = sgt.query( L +1, R -1);
               if( y - x +1> R - L +1){
                       if( a[ R ].y == y && a[ L ].y == x ){
                               if( a[ R ].r > a[ L ].r )printf("false\n");else{
                                      if( X >= a[ R ].r )printf("false\n");else printf("maybe\n");
                               }
                       }else{
                               if( a[ L ].y == x &&( X >= a[ L ].r ||( a[ R ].y > x && a[ R ].r > a[ L ].r ))){
                                      printf("false\n");
                                      continue;
                               }
                               if( a[ R ].y == y &&( X>= a[ R ].r ||( a[ L ].y < y && a[ L ].r > a[ R ].r )))printf("false\n");else printf("maybe\n");
                       }
               }else{
                       if( a[ R ].r <= a[ L ].r && X < a[ R ].r )printf("true\n");else printf("false\n");
               }
        }
        return 0;
}