分数

目的

分数の加減乗を扱うためのクラス。オーバーフローに気をつけて下さい。

使い方

public Fraction(long x,long y)
$\frac{x}{y}$を表すクラスを作成
Fraction add(Fraction o)
自分自身と分数oとの和をreturn
Fraction subtract(Fraction o)
自分自身と分数oとの差をreturn
Fraction mul(Fraction o)
自分自身と分数oとの積をreturn
Fraction equiv(Fraction o)
自分自身と分数oが等しいかどうか判定

ソースコード

class SegTree {
	int n;
	long[] val;
	
	public SegTree(int n_) {
		n = 1;
		while (n < n_)
			n *= 2;
		val = new long[2 * n - 1];
		Arrays.fill(val, Long.MAX_VALUE / 3);
	}

	void setVal(int k, long v) {
		k += n - 1;
		val[k] = Math.min(val[k], v);
		while (k > 0) {
			k = (k - 1) / 2;
			val[k] = Math.min(val[2 * k + 1], val[2 * k + 2]);
		}
	}

	void addVal(int k, long v) {
		k += n - 1;
		val[k] += v;
		while (k > 0) {
			k = (k - 1) / 2;
			val[k] = Math.min(val[2 * k + 1], val[2 * k + 2]);
		}
	}

	long query(int a, int b, int l, int r, int k) {
		if (a <= l && r <= b) {
			return val[k];
		} else  if (r <= a || b <= l) {
			return Long.MAX_VALUE / 3;
		} else  {
			return Math.min(query(a, b, l, (l + r) / 2, 2 * k + 1), query(a, b, (l + r) / 2, r, 2 * k + 2));
		}
	}
		long query(int a, int b) {
		return query(a, b, 0, n, 0);
	}
}	

Verified

yukicoder No.461 三角形はいくつ?