This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
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