This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
package library.ds; import java.util.function.LongBinaryOperator; import java.util.function.LongPredicate; /** * SparseTable */ public final class SparseTable { private final long[][] st; private final int[] lookup; private final LongBinaryOperator op; /** * コンストラクタ * @param a 配列 * @param op 二項演算 */ public SparseTable(final int[] a, final LongBinaryOperator op) { this.op = op; int b = 0; while((1 << b) <= a.length) { ++b; } st = new long[b][1 << b]; for(int i = 0; i < a.length; i++) { st[0][i] = a[i]; } for(int i = 1; i < b; i++) { for(int j = 0; j + (1 << i) <= (1 << b); j++) { st[i][j] = op.applyAsLong(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } lookup = new int[a.length + 1]; for(int i = 2; i < lookup.length; i++) { lookup[i] = lookup[i >> 1] + 1; } } /** * コンストラクタ * @param a 配列 * @param op 二項演算 */ public SparseTable(final long[] a, final LongBinaryOperator op) { this.op = op; int b = 0; while((1 << b) <= a.length) { ++b; } st = new long[b][1 << b]; for(int i = 0; i < a.length; i++) { st[0][i] = a[i]; } for(int i = 1; i < b; i++) { for(int j = 0; j + (1 << i) <= (1 << b); j++) { st[i][j] = op.applyAsLong(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } lookup = new int[a.length + 1]; for(int i = 2; i < lookup.length; i++) { lookup[i] = lookup[i >> 1] + 1; } } /** * 半開区間[l, r)についての二項演算結果を返す * @param l * @param r * @return 半開区間[l, r)について二項演算した結果 */ public final long query(final int l, final int r) { final int b = lookup[r - l]; return op.applyAsLong(st[b][l], st[b][r - (1 << b)]); } /** * 特定の条件を満たす最も左の位置を二分探索で探す * @param x * @param fn */ public final int minLeft(final int x, final LongPredicate fn) { if(x == 0) { return 0; } int ok = x, ng = -1; while(Math.abs(ok - ng) > 1) { final int mid = (ok + ng) / 2; if(fn.test(query(mid, x) - 1)) { ok = mid; } else { ng = mid; } } return ok; } /** * 特定の条件を満たす最も右の位置を二分探索で探す * @param x * @param fn */ public final int maxRight(final int x, final LongPredicate fn) { if(x == lookup.length - 1) { return lookup.length - 1; } int ok = x, ng = lookup.length; while(Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if(fn.test(query(x, mid))) { ok = mid; } else { ng = mid; } } return ok; } }
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/SparseTable.java