This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
package library.ds.waveletmatrix; import library.core.Utility; import library.ds.pair.IntPair; /** * @see WaveletMatrix */ public final class WaveletMatrixBeta { private final int log; private final SuccinctIndexableDictionary[] matrix; private final int[] mid; WaveletMatrixBeta(final long[] arr, final int log) { final int len = arr.length; this.log = log; matrix = new SuccinctIndexableDictionary[log]; mid = new int[log]; final long[] l = new long[len], r = new long[len]; for(int level = log; --level >= 0;) { matrix[level] = new SuccinctIndexableDictionary(len + 1); int left = 0, right = 0; for(int i = 0; i < len; ++i) { if(((arr[i] >> level) & 1) == 1) { matrix[level].set(i); r[right++] = arr[i]; } else { l[left++] = arr[i]; } } mid[level] = left; matrix[level].build(); final long[] tmp = new long[len]; System.arraycopy(arr, 0, tmp, 0, len); System.arraycopy(l, 0, arr, 0, len); System.arraycopy(tmp, 0, l, 0, len); for(int i = 0; i < right; ++i) { arr[left + i] = r[i]; } } } private final IntPair succ(final boolean f, final int l, final int r, final int level){ return IntPair.of(matrix[level].rank(f, l) + mid[level] * (f ? 1 : 0), matrix[level].rank(f, r) + mid[level] * (f ? 1 : 0)); } final long access(int k) { long ret = 0; for(int level = log; --level >= 0;) { final boolean f = matrix[level].get(k); if(f) { ret |= 1L << level; } k = matrix[level].rank(f, k) + mid[level] * (f ? 1 : 0); } return ret; } final int rank(final long x, int r) { int l = 0; for(int level = log; --level >= 0;) { final IntPair p = succ(((x >> level) & 1) == 1, l, r, level); l = p.first.intValue(); r = p.second.intValue(); } return r - l; } final long kthMin(int l, int r, int k) { if(!Utility.scope(0, k, r - l - 1)) { throw new IndexOutOfBoundsException(); } long ret = 0; for(int level = log; --level >= 0;) { final int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l); final boolean f = cnt <= k; if(f) { ret |= 1 << level; k -= cnt; } final IntPair p = succ(f, l, r, level); l = p.first.intValue(); r = p.second.intValue(); } return ret; } final long kthMax(final int l, final int r, final int k){ return kthMin(l, r, r - l - k - 1); } final int rangeFreq(int l, int r, final long upper) { int ret = 0; for(int level = log; --level >= 0;) { final boolean f = ((upper >> level) & 1) == 1; if(f) { ret += matrix[level].rank(false, r) - matrix[level].rank(false, l); } final IntPair p = succ(f, l, r, level); l = p.first.intValue(); r = p.second.intValue(); } return ret; } final int rangeFreq(final int l, final int r, final long lower, final long upper){ return rangeFreq(l, r, upper) - rangeFreq(l, r, lower); } final long prev(final int l, final int r, final long upper) { final int cnt = rangeFreq(l, r, upper); return cnt == 0 ? -1 : kthMin(l, r, cnt - 1); } final long next(final int l, final int r, final long lower) { final int cnt = rangeFreq(l, r, lower); return cnt == r - l ? -1 : kthMin(l, r, cnt); } }
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/waveletmatrix/WaveletMatrixBeta.java