Codeforces Round #307 Div2 E: GukiZ and GukiZiana

問題

codeforces.com

解法

平方分割を用いる。与えられたN個の数字をの配列に入れる。個で1ブロックと考え、ブロック全体がカバーされている加算操作に対しては、別の場所に記録しておく。

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
	private long[][] blocks;
	private ArrayList<HashSet<Long>> checkList;
	private long[] add;
	private int N, SIZE_OF_BLOCK;

	public void solve() {
		N = nextInt();
		SIZE_OF_BLOCK = (int) Math.sqrt(N);// 1ブロックのサイズ
		int Q = nextInt();
		int[] array = new int[N];
		for (int i = 0; i < N; i++) {
			array[i] = nextInt();
		}

		int BLOCK_NUM = N / SIZE_OF_BLOCK + 1;// ブロックの数
		checkList = new ArrayList<>();// 探している数がブロックに含まれているかどうかを確かめるリスト
		for (int i = 0; i < BLOCK_NUM; i++) {
			checkList.add(new HashSet<Long>());
		}

		blocks = new long[BLOCK_NUM][SIZE_OF_BLOCK];
		for (int i = 0; i < N; i++) {
			int block = i / SIZE_OF_BLOCK;
			int idx = i % SIZE_OF_BLOCK;
			blocks[block][idx] = array[i];
			checkList.get(block).add(blocks[block][idx]);
		}

		add = new long[BLOCK_NUM];// ブロック全体への加算を記録する

		StringBuilder ans = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			int type = nextInt();
			if (type == 1) {
				// 加算クエリ
				int from = nextInt() - 1;
				int to = nextInt() - 1;
				int addition = nextInt();

				int fromBlock = from / SIZE_OF_BLOCK;// fromが属しているブロック
				int toBlock = to / SIZE_OF_BLOCK;// toが属しているブロック
				if (fromBlock == toBlock) {
					// 1ブロック内の操作の時
					if (from % SIZE_OF_BLOCK == 0 && (to + 1) % SIZE_OF_BLOCK == 0) {
						// ブロックの端から端までの加算なら、addに記録する
						add[fromBlock] += addition;
					} else {
						// そうでなければ配列に直接足す
						add2Array(from, to, addition);
					}
					continue;
				}

				if (from % SIZE_OF_BLOCK != 0) {
					// 先頭部分がブロックからはみ出ている時
					int headTo = (fromBlock + 1) * SIZE_OF_BLOCK - 1;
					add2Array(from, headTo, addition);
					fromBlock++;
				}
				if ((to + 1) % SIZE_OF_BLOCK != 0) {
					int tailFrom = toBlock * SIZE_OF_BLOCK;
					add2Array(tailFrom, to, addition);
					toBlock--;
				}

				for (int i = fromBlock; i <= toBlock; i++) {
					// ブロック全体への操作はaddに記録する
					add[i] += addition;
				}
			} else {
				// 検索クエリ
				int target = nextInt();

				// 全てのブロックのチェックリストを先頭から見ていき、含まれているブロックがあれば
				// そのブロックを先頭から見ていく
				int first = -1;
				searchFirst: for (int block = 0; block < BLOCK_NUM; block++) {
					if (checkList.get(block).contains(target - add[block])) {
						for (int i = 0; i < SIZE_OF_BLOCK; i++) {
							if (blocks[block][i] + add[block] == target) {
								first = block * SIZE_OF_BLOCK + i;
								break searchFirst;
							}
						}
					}
				}
				if (first == -1) {
					// 見つからなかった時
					ans.append(-1 + "\n");
					continue;
				}

				int last = first;
				searchLast: for (int block = BLOCK_NUM - 1; block >= 0; block--) {
					if (checkList.get(block).contains(target - add[block])) {
						for (int i = SIZE_OF_BLOCK - 1; i >= 0; i--) {
							if (block * SIZE_OF_BLOCK + i >= N) {
								continue;
							}

							if (blocks[block][i] + add[block] == target) {
								last = block * SIZE_OF_BLOCK + i;
								break searchLast;
							}
						}
					}
				}
				ans.append((last - first) + "\n");
			}
		}
		System.out.print(ans.toString());

	}

	private void add2Array(int from, int to, int addition) {
		// 配列に直接足す操作
		for (int i = from; i <= to; i++) {
			int block = i / SIZE_OF_BLOCK;
			int idx = i % SIZE_OF_BLOCK;
			blocks[block][idx] += addition;
		}

		// チェックリストを作り直す
		int block = to / SIZE_OF_BLOCK;
		checkList.get(block).clear();
		for (int i = 0; i < SIZE_OF_BLOCK; i++) {
			if (block * SIZE_OF_BLOCK + i >= N) {
				break;
			}
			blocks[block][i] += add[block];
			checkList.get(block).add(blocks[block][i]);
		}
		add[block] = 0;
	}

	private int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}