LA 6531 Go up the Ultras 单调栈+RMQ - c++编程基础

题意：已经懒得吐槽了。。有N个山峰，(N<=10^5)，每个山峰有高度h，对应着每个山峰有一个d值，每个山峰到所有其他的严格比

它高的山峰都会经过一个最低值（山谷），d代表是h减去这些最低值中的最大值的差（如果不存在比它高的山峰那么d就是它本身的

高度），问有多少山峰的d>=150000米。

思路：利用单调栈维护每个峰左边第一个比它高的峰的位置l，右边第一个比它高的峰的位置r，对于r，我们从前向后维护一个单调减

序列，如果当前考虑的点i比栈顶的元素高度高，那么弹出栈顶元素，并将它的r置为i，直到栈顶元素的高度大于等于i的高度。对于l,

从后往前维护单调减序列。对于每个点，求[ l[ i ] , i ] 的最小值d1,[ i , r[ i ] ]的最小值d2，求个最大值d=max(d1,d2)，然后看是否h[i]-

d>=150000，是就输出，可以RMQ预处理一段区间的最小值，详见代码：

/*********************************************************
  file name: LA6531.cpp
  author : kereo
  create time:  2015年02月06日 星期五 17时00分19秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=20; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int n; int dp[MAXN][N]; struct node{ int l,r,h; }p[MAXN]; stack
              
               s; int RMQ(int l,int r){ int k=0; while((1<<(k+1))<=r-l+1) k++; return min(dp[l][k],dp[r-(1<
               
                =p[i].h){ s.push(i); } else{ while(!s.empty() && p[s.top()].h
                
                 =1;i--){ if(s.empty()) s.push(i); else if(p[s.top()].h>=p[i].h) s.push(i); else{ while(!s.empty() && p[s.top()].h
                 
                  =150000){ if(flag){ printf("%d",i); flag=0; } else printf(" %d",i); } } printf("\n"); } return 0; }