3624-Balanced Lineup

問題（外部リンク）

3264 -- Balanced Lineup

実装の概要

今回の問題で重要なのはある区間における最小値と最大値なので、それぞれをセグメント木で管理することで高速に処理を行うことができます。（クエリ数が多いので、その都度ループを回して区間内を探索すると間に合いません）
１つのセグメント木で両方とも管理することも可能だと思いますが、この実装ではそれぞれ別のクラスとして作成しました。
ただ、ほぼ似通った処理も多いためabstractなセグメント木のクラスを作成しそれを継承する形を採っています。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmpArray = br.readLine().split(" ");
		
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);
		
		int height[] = new int[n];
		MinSegmentTree minseg = new MinSegmentTree(n);
		MaxSegmentTree maxseg = new MaxSegmentTree(n);

		//セグメント木の値更新
		for(int i = 0; i < n; i++){
			height[i] = Integer.parseInt(br.readLine());
			minseg.update(i, height[i]);
			maxseg.update(i, height[i]);
		}
		
		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]);
			int to = Integer.parseInt(tmpArray[1]);
			
			//問題が1-indexedなので1ずらす
			int min = minseg.query(from - 1, to);
			int max = maxseg.query(from - 1, to);
			
			//fromとtoが同じ場合は差はないはず
			if(from == to){
				min = 0;
				max = 0;
			}
			
			System.out.println(max - min);
		}
		
	}

}
//抽象的なセグメント木
abstract class SegmentTree {
	protected int n;
	protected int[] data;
	private int initValue;
	
	//nは要素の個数、initValueは目的に応じて初期化の値を変えること
	SegmentTree(int n, int initValue){
		
		this.n = 1;
		while (this.n < n){
			this.n *= 2;
		}
		
		this.data = new int[this.n*2 - 1];

		this.initValue = initValue;
		initData();
	}
		
	private void initData(){
		Arrays.fill(data, initValue);
	}
	
	void update(int k, int a){
		k += n - 1;
		data[k] = a;
		while(k > 0){
			k = (k - 1) / 2;
			data[k] = choose(data[k * 2 + 1], data[k * 2 + 2]);
		}
	}

	//目的に合わせて値選択のための処理を実装すること
	abstract protected int choose(int a, int b);
	
	//[a, b)までの範囲から目的の値を探す
	public int query(int a, int b){
		return query(a, b, 0, 0, this.n);
	}
	
	private int query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l){
			return initValue;
		}
		
		if(a <= l && r <= b){
			return data[k];
		}
		else {
			int vl = query(a, b, k*2 + 1, l, (l + r)/2);
			int vr = query(a, b, k*2 + 2, (l + r) / 2, r);
			return choose(vl, vr);
		}
	}

}

//最小値の管理のためのセグメント木
class MinSegmentTree extends SegmentTree {

	MinSegmentTree(int n) {
		super(n, Integer.MAX_VALUE);
	}
	
	@Override
	protected int choose(int a, int b) {
		return Math.min(a, b);
	}
	
}

//最大値の管理のためのセグメント木
class MaxSegmentTree extends SegmentTree {

	MaxSegmentTree(int n) {
		super(n, Integer.MIN_VALUE);
	}

	@Override
	protected int choose(int a, int b) {
		return Math.max(a, b);
	}
	
}