VvyLw's Library

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

View the Project on GitHub

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

Depends on

Required by

Code

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.12/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.12/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
Back to top page