学步园

士兵杀敌（三）

描述

南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。

所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。

现在，请你写一个程序，帮小工回答南将军每次的询问吧。

注意，南将军可能询问很多次。

输入

只有一组测试数据
第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1
随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的杀敌数。
再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。

输出

对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。

样例输入

5 2
1 2 6 9 3
1 2
2 4

样例输出

1
7

来源

经典改编

上传者

张云聪

这道题比较有意义，我使用了线段树，伪ST算法(主要是还没理解ST算法的含义就开始动手) ST算法实现

下面放代码

import java.util.Scanner;

//线段树的一种实现方式 TL

public class SoldierKillEnemy3V1 {
    int[][]
tree; // tree[n][0]存子节点中最小的树 类推
    int
size;

    public
static void main(String[] args) {
  
    
SoldierKillEnemy3V1 main = new SoldierKillEnemy3V1();
  
    
main.solution();
    }

    public void
solution() {
  
    
Scanner in = new Scanner(System.in);
  
    
size = in.nextInt();
  
    
int cmds = in.nextInt();
  
    
tree = new int[size * 4 + 1][2];
  
    
init();

  
    
for (int i = 1; i <= size; i++) {
  
    
    Update(i,
in.nextInt());
  
    
}
  
    
int start = 0;
  
    
int end = 0;
  
    
for (int i = 1; i <= cmds; i++) {
  
    
    start =
in.nextInt();
  
    
    end =
in.nextInt();
  
    
   
System.out.println(QueryMax(start, end) - QueryMin(start,
end));
  
    
}       

    }

    public void
init() {
  
    
for (int i = 0; i < tree.length; i++) {
  
    
    tree[i][0] =
Integer.MAX_VALUE;
  
    
    tree[i][1] =
Integer.MIN_VALUE;
  
    
}
    }

    //
在这条线段中的n节点 插入权值value；
    public void
Update(int n, int value) {
  
    
Update(1, 1, size, n, value);
    }

    private void
Update(int index, int left, int right, int n, int value) {
  
    
tree[index][0] = Math.min(tree[index][0], value);
  
    
tree[index][1] = Math.max(tree[index][1], value);
  
    
if (left == right) {
  
    
   
return;
  
    
} else {
  
    
    int mid =
(left + right) >> 1;
  
    
    if (mid
>= n) {