ARC 035D: 高橋くんとマラソンコース (セグメント木)

問題

D: 高橋くんとマラソンコース - AtCoder Regular Contest 035 | AtCoder

解法

チェックポイント間の経路数はものすごく大きくなるのでlogで保存しておく。クエリに対してチェックポイント間の経路数の和を返すので、和のセグメント木を作っておく。

コード

import java.io.IOException;

public class Main {
	private static double[] segtree;
	private static int[][] cP;
	private static int MAX_N;

	public static void main(String[] args) {
		int N = nextInt();
		cP = new int[N][2];
		for (int i = 0; i < cP.length; i++) {
			cP[i][0] = nextInt();
			cP[i][1] = nextInt();
		}

		// チェックポイントnからチェックポイントn+1へ行く時の経路の組み合わせをpatterns[n]に入れておく
		// logで入れておく
		MAX_N = 1;
		while (N > MAX_N) {
			MAX_N *= 2;
		}
		segtree = new double[2 * MAX_N - 1];
		for (int i = 0; i < N - 1; i++) {
			combi(i);
		}

		int Q = nextInt();
		for (int i = 0; i < Q; i++) {
			int t = nextInt();
			if (t == 1) {
				int k = nextInt() - 1;
				cP[k][0] = nextInt();
				cP[k][1] = nextInt();
				if (k > 0) {
					combi(k - 1);
				}
				if (k < N - 1) {
					combi(k);
				}
			} else {
				int l1 = nextInt() - 1;
				int r1 = nextInt() - 1;
				double first = querySegTree(l1, r1);

				int l2 = nextInt() - 1;
				int r2 = nextInt() - 1;
				double second = querySegTree(l2, r2);
				if (first > second) {
					System.out.println("FIRST");
				} else {
					System.out.println("SECOND");
				}
			}
		}
	}

	static void updateSegTree(int k, double a) {
		k += MAX_N - 1;
		segtree[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			segtree[k] = segtree[k * 2 + 1] + segtree[k * 2 + 2];
		}
	}

	static double querySegTree(int a, int b) {
		return querySegTree(a, b, 0, 0, MAX_N);
	}

	static double querySegTree(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return 0;
		}
		if (a <= l && r <= b) {
			return segtree[k];
		}
		int m = (l + r) / 2;
		return (querySegTree(a, b, 2 * k + 1, l, m) + querySegTree(a, b, 2 * k + 2, m, r));
	}

	static void combi(int n) {
		// チェックポイントnからチェックポイントn+1へ行く時の経路の組み合わせをpatterns[n]に入れておく
		int x = Math.abs(cP[n][0] - cP[n + 1][0]);
		int y = Math.abs(cP[n][1] - cP[n + 1][1]);
		int min = Math.min(x, y);
		int max = x + y;
		// maxCminをもとめる
		double p = 0;
		for (int j = max; j > max - min; j--) {
			p += Math.log(j);
		}
		for (int j = 2; j <= min; j++) {
			p -= Math.log(j);
		}
		updateSegTree(n, p);
	}

	static 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;
	}
}