VvyLw's Library

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

View the Project on GitHub

:warning: Java/library/ds/waveletmatrix/WaveletMatrixBeta.java

Depends on

Required by

Code

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