OJ题号：

洛谷2880

思路1：

线段树维护区间最大最小值。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 inline int getint() { 6     char ch; 7     bool sgn=false; 8     while(!isdigit(ch=getchar())) if(ch=='-') sgn=true; 9     int x=ch^'0';10     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');11     return sgn?-x:x;12 }13 const int inf=0x7fffffff;14 const int N=50001;15 class SegmentTree {16     #define _left <<117     #define _right <<1|118     private:19         int max[N<<2],min[N<<2];20         void push_up(const int p) {21             max[p]=std::max(max[p _left],max[p _right]);22             min[p]=std::min(min[p _left],min[p _right]);23         }24     public:25         void build(const int p,const int b,const int e) {26             if(b==e) {27                 max[p]=min[p]=getint();28                 return;29             }30             int mid=(b+e)>>1;31             build(p _left,b,mid);32             build(p _right,mid+1,e);33             push_up(p);34         }35         std::pair
         
           query(const int p,const int b,const int e,const int l,const int r) {36             if((b==l)&&(e==r)) {37                 return std::make_pair(max[p],min[p]);38             }39             int mid=(b+e)>>1;40             int max=0,min=inf;41             if(l<=mid) {42                 std::pair
          
            tmp=query(p _left,b,mid,l,std::min(mid,r));43 max=std::max(max,tmp.first);44 min=std::min(min,tmp.second);45 }46 if(r>mid) {47 std::pair
           
             tmp=query(p _right,mid+1,e,std::max(mid+1,l),r);48 max=std::max(max,tmp.first);49 min=std::min(min,tmp.second);50 }51 return std::make_pair(max,min);52 }53 };54 SegmentTree t;55 int main() {56 int n=getint(),m=getint();57 t.build(1,1,n);58 while(m--) {59 int l=getint(),r=getint();60 std::pair
            
              tmp=t.query(1,1,n,l,r);61 printf("%d\n",tmp.first-tmp.second);62 }63 return 0;64 }
            
           
          
         
        
       
      
     

 思路2：

倍增法求RMQ。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 inline int getint() { 6     char ch; 7     while(!isdigit(ch=getchar())); 8     int x=ch^'0'; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10     return x;11 }12 const int N=50001,logN=log2(N)+1;13 int min[N][logN],max[N][logN];14 int main() {15     int n=getint(),m=getint();16     for(int i=1;i<=n;i++) {17         min[i][0]=max[i][0]=getint();18     }19     for(int j=1;j<=log2(n);j++) {20         for(int i=1;i<=n-(1<