3368-Frequent values

問題（外部リンク）

3368 -- Frequent values

実装の概要

指定された区間の中で最も長く同じ数字が続いた箇所の長さを求める問題です。要素数とクエリ数が多いためその都度ループを回すと間に合いません。
そこで今回はセグメント木を使います。ただし区間内の最大値を求める問題と比べると実装の際に考慮しなければならない箇所が多いと思います。
以下の実装ではセグメント木のそれぞれの要素自体に

• その区間内で同じ数字が続く最長の長さ
• 左端から同じ数字が続く最長の長さ
• 右端から同じ数字が続く最長の長さ
• 左端の数字
• 右端の数字

を保持させています。
最長の長さを求める場合等には右の区間と左の区間にまたがる可能性なども考慮しながら処理する必要があります。
今回の実装はだいぶコード長があるため、より簡潔に書く方法を思いつき次第書き直したいと思います。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input = br.readLine();

			if(input.equals("0")){
				break;
			}

			String[] tmpArray = input.split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int q = Integer.parseInt(tmpArray[1]);

			MaxLengthSegmentTree maxseg = new MaxLengthSegmentTree(n);

			int array[] = new int[n];
			tmpArray = br.readLine().split(" ");
			for(int i = 0; i < n; i++){
				array[i] = Integer.parseInt(tmpArray[i]);

				maxseg.update(i, array[i]);
			}

			for(int i = 0; i < q; i++){
				tmpArray = br.readLine().split(" ");

				//あえて開区間としてクエリを投げる
				int from = Integer.parseInt(tmpArray[0]) - 1;
				int to = Integer.parseInt(tmpArray[1]);

				System.out.println(maxseg.query(from, to));
			}
		}
	}

}

class MaxLengthSegmentTree {
	protected int n;
	protected Node[] data;

	//nは要素の個数
	MaxLengthSegmentTree(int n){

		//要素数を2のべき乗にしておく
		this.n = 1;
		while (this.n < n){
			this.n *= 2;
		}

		this.data = new Node[this.n*2 - 1];

		initData();
	}

	private void initData(){
		for(int i = 0; i < this.data.length; i++){
			this.data[i] = new Node();
		}
	}

	//for debug
	void show(){
		System.out.println("Data info");
		for(int i = 0; i < this.data.length; i++){
			System.out.println("i = "+ i + " " + this.data[i].toString());
		}
	}

	void update(int k, int a){
		k += n - 1;

		//区間長が1なら右の数字も左の数字もa
		data[k].leftNum = a; data[k].rightNum = a;

		while(k > 0){
			k = (k - 1) / 2;

			int l = k * 2 + 1;
			int r = k * 2 + 2;

			//leftの更新
			//2区間を連結可能な場合
			if(data[l].leftNum == data[r].leftNum && data[l].rightNum == data[r].leftNum){
				data[k].leftLen = data[l].leftLen + data[r].leftLen;
			}
			//連結できないならそのままleftLenを引き継ぐ
			else {
				data[k].leftLen = data[l].leftLen;
			}
			data[k].leftNum = data[l].leftNum;

			//rightの更新
			if(data[r].rightNum == data[l].rightNum && data[l].rightNum == data[r].leftNum){
				data[k].rightLen = data[l].rightLen + data[r].rightLen;
			}
			else {
				data[k].rightLen = data[r].rightLen;
			}
			data[k].rightNum = data[r].rightNum;

			//midの更新
			//子セグメントのうち長い方
			data[k].midLen = Math.max(data[l].midLen, data[r].midLen);
			//連結可能かつ繋げた部分の方が長い場合は更新
			if(data[l].rightNum == data[r].leftNum){
				data[k].midLen = Math.max(data[k].midLen, data[l].rightLen + data[r].leftLen);
			}
		}
	}

	//[a, b)までの範囲から目的の値を探す
	public int query(int a, int b){
		return query(a, b, 0, 0, this.n).midLen;
	}

	private Node query(int a, int b, int k, int l, int r) {
		// [a, b)と[l, r)が交差しない
		if(r <= a || b <= l){
			return null;
		}

		// [a, b)が[l, r)を完全に含んでいる
		if(a <= l && r <= b){
			return data[k];
		}

		//そうでない場合は子セグメントに再帰的に処理を行う
		else {
			Node vl = query(a, b, k*2 + 1, l, (l + r)/2);
			Node vr = query(a, b, k*2 + 2, (l + r) / 2, r);

			if(vl == null){
				return vr;
			}
			else if(vr == null){
				return vl;
			}

			int result = Math.max(vl.midLen, vr.midLen);
			int left = vl.leftLen;
			//連結可能な場合
			if(vl.leftNum == vr.leftNum){
				left = vl.leftLen + vr.leftLen;
			}

			int right = vr.rightLen;
			if(vl.rightNum == vr.rightNum){
				right = vl.rightLen + vr.rightLen;
			}

			if(vl.rightNum == vr.leftNum){
				result = Math.max(result, vl.rightLen + vr.leftLen);
			}

			return new Node(result, left, right, vl.leftNum, vr.rightNum);
		}
	}

}
class Node {
	int midLen = 1;
	int leftLen = 1;
	int rightLen = 1;
	int leftNum = Integer.MAX_VALUE;
	int rightNum = Integer.MIN_VALUE;

	Node(){
		this(1, 1, 1, Integer.MAX_VALUE, Integer.MIN_VALUE);
	}

	Node(int mid, int ll, int rl, int ln, int rn){
		this.midLen = mid;
		this.leftLen = ll;
		this.rightLen = rl;
		this.leftNum = ln;
		this.rightNum = rn;
	}

	public String toString(){
		return "left "+leftLen+" mid "+midLen + " right " + rightLen + " leftNum "+ leftNum + " rightNum "+rightNum;
	}
}