VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:warning: Java/library/ds/SegmentTree.java

Depends on

Required by

Code

package library.ds;

import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;
import java.util.stream.IntStream;

/**
 * セグメント木
 * @param <T>
 * @see <a href="https://github.com/tatyam-prime/kyopro_library/blob/master/SegmentTree.cpp">参考元</a>
 */
public final class SegmentTree<T> {
	private int n = 1, rank = 0, fini;
	private final BinaryOperator<T> op;
	private final T e;
	private final Object[] dat;
	/**
	 * コンストラクタ
	 * @param fini サイズ
	 * @param op 二項演算
	 * @param e 単位元
	 */
	public SegmentTree(final int fini, final BinaryOperator<T> op, final T e) {
		this.fini = fini;
		this.op = op;
		this.e = e;
		while(this.fini > n) {
			n <<= 1;
			rank++;
		}
		dat = new Object[2 * n];
		Arrays.fill(dat, e);
	}
	/**
	 * コンストラクタ
	 * @param a ボクシングされた配列
	 * @param op
	 * @param e
	 */
	public SegmentTree(final T[] a, final BinaryOperator<T> op, final T e) {
		this(a.length, op, e);
		IntStream.range(0, a.length).forEach(i -> update(i, a[i]));
	}
	/**
	 * i番目の要素をxにする
	 * @param i
	 * @param x
	 */
	@SuppressWarnings("unchecked")
	public final void update(int i, final T x) {
		i += n;
		dat[i] = x;
		do {
			i >>= 1;
			dat[i] = op.apply((T) dat[2 * i], (T) dat[2 * i + 1]);
		} while(i > 0);
	}
	/**
	 * SegmentTree[i]を返す
	 * @param i
	 * @return i番目の要素
	 */
	public final T get(final int i){ return query(i, i + 1); }
	/**
	 * 半開区間[l, r)に対しての二項演算結果を返す
	 * @param a
	 * @param b
	 * @return 半開区間[l, r)に対して二項演算した結果
	 */
	@SuppressWarnings("unchecked")
	public final T query(int a, int b) {
		T l = e, r = e;
		for(a += n, b += n; a < b; a >>= 1, b >>= 1) {
			if(a % 2 == 1) {
				l = op.apply(l, (T) dat[a++]);
			}
			if(b % 2 == 1) {
				r = op.apply((T) dat[--b], r);
			}
		}
		return op.apply(l, r);
	}
	/**
	 * 全体の二項演算結果を返す
	 * @return 全体を二項演算した結果
	 */
	@SuppressWarnings("unchecked")
	final T all(){ return (T) dat[1]; }
	/**
	 * 特定の条件を満たす最も左の位置を探す
	 * @param r
	 * @param fn
	 */
	@SuppressWarnings("unchecked")
	public final int findLeft(final int r, final Predicate<T> fn) {
		if(r == 0) {
			return 0;
		}
		int h = 0, i = r + n;
		T val = e;
		for(; h <= rank; h++) {
			if(((i >> h) & 1) != 0) {
				final T val2 = op.apply(val, (T) dat[i >> (h ^ 1)]);
				if(fn.test(val2)) {
					i -= 1 << h;
					if(i == n) {
						return 0;
					}
					val = val2;
				} else {
					break;
				}
			}
		}
		for(; h-- > 0;) {
			final T val2 = op.apply(val, (T) dat[(i >> h) - 1]);
			if(fn.test(val2)) {
				i -= 1 << h;
				if(i == n) {
					return 0;
				}
				val = val2;
			}
		}
		return i - n;
	}
	/**
	 * 特定の条件を満たす最も右の位置を探す
	 * @param l
	 * @param fn
	 */
	@SuppressWarnings("unchecked")
	public final int findRight(final int l, final Predicate<T> fn) {
		if(l == fini) {
			return fini;
		}
		int h = 0, i = l + n;
		T val = e;
		for(; h <= rank; h++) {
			if(((i >> h) & 1) != 0) {
				final T val2 = op.apply(val, (T) dat[i >> h]);
				if(fn.test(val2)) {
					i += 1 << h;
					if(i == n * 2) {
						return fini;
					}
					val = val2;
				} else {
					break;
				}
			}
		}
		for(; h-- > 0;) {
			final T val2 = op.apply(val, (T) dat[i>>h]);
			if(fn.test(val2)) {
				i += 1 << h;
				if(i == n * 2) {
					return fini;
				}
				val = val2;
			}
		}
		return Math.min(i - n, fini);
	}
	/**
	 * SegmentTreeを配列に変換したものを返す
	 * @return SegmentTreeの配列
	 */
	@SuppressWarnings("unchecked")
	public final T[] toArray(){ return (T[]) IntStream.range(0, fini).mapToObj(i -> get(i)).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < fini;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}
Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/library/ds/SegmentTree.java
Back to top page