library/WaveletMatrix.java

• View this file on GitHub
• Last update: 2023-03-23 19:06:36+09:00

Depends on

• library/BitVector.java
• library/FastIO.java

Required by

• library/CompressedWaveletMatrix.java

Verified with

• library/WaveletMatrix_freq_test.java
• library/WaveletMatrix_smallest_test.java

Code

package library;

import library.FastIO;
import library.BitVector;

class WaveletMatrix {
	final int bitSize;
	final int n;
	BitVector mat[];
	int mid[];
	final int max;

	// O(NlogA)
	WaveletMatrix(int[] a) {
		n = a.length;
		long tmp = 1;
		for(int i = 0; i < n; i ++) tmp = Math.max(tmp, a[i]);
		bitSize = n == 0 ? 1 : Long.numberOfTrailingZeros(Long.highestOneBit(tmp)) + 1;
		max = 1 << bitSize;
		mat = new BitVector[bitSize];
		mid = new int[bitSize];
		for(int i = bitSize - 1; i >= 0; i --) {
			mat[i] = new BitVector(n);
			int a2[] = new int[n];
			int idx = 0;
			for(int j = 0; j < n; j ++) if((a[j] >> i & 1) == 0) a2[idx ++] = a[j];
			mid[i] = idx;
			for(int j = 0; j < n; j ++) if((a[j] >> i & 1) != 0) { a2[idx ++] = a[j]; mat[i].set(j); }
			a = a2;
			mat[i].init();
		}
	}

	// Query: O(logVloglogN)

	// a_i
	final int get(int k) {
		FastIO.rangeCheck(k, n);
		int val = 0;
		for(int i = bitSize - 1; i >= 0; i --) {
			boolean b = mat[i].get(k);
			k = mat[i].rank(b, k);
			if(b) { val |= 1 << i; k += mid[i]; }
		}
		return val;
	}

	// count x in [0, k)
	final int rank(int x, int k) { return rank(x, 0, k); }
	// count x in [l, r)
	final int rank(int x, int l, int r) {
		FastIO.inclusiveRangeCheck(l, n);
		FastIO.inclusiveRangeCheck(r, n);
		FastIO.assertion(l <= r);
		if(x < 0 || x >= max) return 0;
		for(int i = bitSize - 1; i >= 0; i --) {
			boolean b = (x >> i & 1) != 0;
			l = mat[i].rank(b, l); if(b) l += mid[i];
			r = mat[i].rank(b, r); if(b) r += mid[i];
		}
		return r - l;
	}

	// position of k-th occurrence of x
	final int select(int x, int k) {
		FastIO.nonNegativeCheck(k);
		if(x < 0 || x >= max) return n;
		int l[] = new int[bitSize + 1];
		int l2[] = new int[bitSize + 1];
		int r = n;
		l[bitSize] = 0;
		for(int i = bitSize - 1; i >= 0; i --) {
			boolean b = (x >> i & 1) != 0;
			l2[i] = mat[i].rank(b, l[i + 1]);
			l[i] = l2[i];
			if(b) l[i] += mid[i];
			r = mat[i].rank(b, r);
			if(b) r += mid[i];
		}
		if(r - l[0] <= k) return n;
		for(int i = 0; i < bitSize; i ++) k = mat[i].select((x >> i & 1) != 0, k + l2[i]) - l[i + 1];
		return k;
	}

	// k-th smallest in [l, r)
	final int smallest(int l, int r, int k) {
		FastIO.nonNegativeCheck(k);
		FastIO.rangeCheck(l, n);
		FastIO.inclusiveRangeCheck(r, n);
		FastIO.assertion(k < r - l);
		int val = 0;
		for(int i = bitSize - 1; i >= 0; i --) {
			int l2 = mat[i].rank(false, l);
			int r2 = mat[i].rank(false, r);
			if(k < r2 - l2) {
				l = l2;
				r = r2;
			}else {
				l += mid[i] - l2;
				r += mid[i] - r2;
				val |= 1 << i;
				k -= r2 - l2;
			}
		}
		return val;
	}
	// k-th largest in [l, r)
	final int largest(int l, int r, int k) { return smallest(l, r, r - l - k - 1); }

	// count [0, x) in [l, r)
	final int lessFreq(int x, int l, int r) {
		FastIO.inclusiveRangeCheck(l, n);
		FastIO.inclusiveRangeCheck(r, n);
		FastIO.assertion(l <= r);
		if(x < 0) return 0;
		if(x >= max) return r - l;
		int cnt = 0;
		for(int i = bitSize - 1; i >= 0; i --) {
			boolean b = (x >> i & 1) != 0;
			int l2 = mat[i].rank(b, l);
			int r2 = mat[i].rank(b, r);
			if(b) cnt += r + l2 - r2 - l;
			l = l2; if(b) l += mid[i];
			r = r2; if(b) r += mid[i];
		}
		return cnt;
	}
	// count [x, ) in [l, r)
	final int greaterFreq(int x, int l, int r) { return r - l - lessFreq(x, l, r); }
	// count [lower, upper) in [l, r)
	final int rangeFreq(int lower, int upper, int l, int r) { return lessFreq(upper, l, r) - lessFreq(lower, l, r); }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/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 "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 71, in bundle
    return subprocess.check_output(shlex.split(command))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 466, in check_output
    return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 571, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['false']' returned non-zero exit status 1.

Back to top page