[NYOJ 119] 士兵杀敌（三）（RMQ ST算法）

题目大意：

有N个士兵，从左到右排成一排，编号从1到N，每个人杀了不同数量的敌人。现在有Q个询问，每次询问要求求出[L,R]区间杀敌做多的和杀敌最少的差。 RMQ ST算法裸题。

/*
ID: wuqi9395@126.com
PROG: beads
LANG: C++
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define PI acos(-1.0) #define maxn 100010 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int N, Q, mx[20][maxn], mn[20][maxn]; void RMQ(int num) { for (int i = 1; i <= log2(num) + 1; i++) for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num) { mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << i >> 1)]); mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i >> 1)]); } } int main () { scanf(%d%d, &N, &Q); for (int i = 1; i <= N; i++) { scanf(%d, &mx[0][i]); mn[0][i] = mx[0][i]; } RMQ(N); int st, ed; while(Q--) { scanf(%d%d, &st, &ed); int k = (int) log2(ed - st + 1.0); int mxans = max(mx[k][st], mx[k][ed - (1 << k) + 1]); int mnans = min(mn[k][st], mn[k][ed - (1 << k) + 1]); printf(%d , mxans - mnans); } return 0; }

[NYOJ 119] 士兵杀敌（三） （RMQ ST算法）

题目大意：