VvyLw's Library

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

View the Project on GitHub

:warning: Java/library/ds/lazysegmenttree/LazySegmentTree.java

Depends on

Required by

Code

package library.ds.lazysegmenttree;

import java.util.Arrays;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;
import java.util.stream.IntStream;

/**
 * 遅延セグ木
 * @see <a href="https://ei1333.github.io/library/structure/segment-tree/lazy-segment-tree.hpp">参考元</a>
 */
public class LazySegmentTree<T, U extends Comparable<? super U>> {
	private final int n;
	private int sz, h;
	private final Object[] data, lazy;
	private final BinaryOperator<T> f;
	private final BiFunction<T, U, T> map;
	private final BinaryOperator<U> comp;
	private final T e;
	private final U id;
	@SuppressWarnings("unchecked")
	private final void update(final int k){ data[k] = f.apply((T) data[2 * k], (T) data[2 * k + 1]); }
	@SuppressWarnings("unchecked")
	private final void allApply(final int k, final U x) {
		data[k] = map.apply((T) data[k], x);
		if(k < sz) {
			lazy[k] = comp.apply((U) lazy[k], x);
		}
	}
	@SuppressWarnings("unchecked")
	private final void propagate(final int k) {
		if(!lazy[k].equals(id)) {
			allApply(2 * k, (U) lazy[k]);
			allApply(2 * k + 1, (U) lazy[k]);
			lazy[k] = id;
		}
	}
	/**
	 * コンストラクタ
	 * @param n サイズ
	 * @param f 二項演算
	 * @param map mapping
	 * @param comp composition
	 * @param e 単位元
	 * @param id
	 */
	public LazySegmentTree(final int n, final BinaryOperator<T> f, final BiFunction<T, U, T> map, final BinaryOperator<U> comp, final T e, final U id) {
		this.n = n;
		this.f = f;
		this.map = map;
		this.comp = comp;
		this.e = e;
		this.id = id;
		sz = 1;
		h = 0;
		while(sz < n) {
			sz <<= 1;
			h++;
		}
		data = new Object[2 * sz];
		Arrays.fill(data, e);
		lazy = new Object[2 * sz];
		Arrays.fill(lazy, id);
	}
	/**
	 * コンストラクタ
	 * @param a ボクシングさせた配列
	 * @param f
	 * @param map
	 * @param comp
	 * @param e
	 * @param id
	 */
	public LazySegmentTree(final T[] a, final BinaryOperator<T> f, final BiFunction<T, U, T> map, final BinaryOperator<U> comp, final T e, final U id) {
		this(a.length, f, map, comp, e, id);
		build(a);
	}
	/**
	 * 構築
	 * @param a
	 */
	public final void build(final T[] a) {
		assert n == a.length;
		for(int k = 0; k < n; ++k) {
			data[k + sz] = a[k];
		}
		for(int k = sz; --k > 0;) {
			update(k);
		}
	}
	/**
	 * k番目の要素をxに更新する
	 * @param k
	 * @param x
	 */
	public final void set(int k, final T x) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		data[k] = x;
		for(int i = 0; ++i <= h;) {
			update(k >> i);
		}
	}
	/**
	 * LazySegmentTree[k]を返す
	 * @param k
	 * @return k番目の要素
	 */
	@SuppressWarnings("unchecked")
	public final T get(int k) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		return (T) data[k];
	}
	/**
	 * 半開区間[l, r)についての二項演算結果を返す
	 * @param l
	 * @param r
	 * @return 半開区間[l, r)について二項演算した結果
	 */
	@SuppressWarnings("unchecked")
	public final T query(int l, int r) {
		if(l >= r) {
			return e;
		}
		l += sz;
		r += sz;
		for(int i = h; i > 0; i--) {
			if(((l >> i) << i) != l) {
				propagate(l >> i);
			}
			if(((r >> i) << i) != r) {
				propagate((r - 1) >> i);
			}
		}
		T l2 = e, r2 = e;
		for(; l < r; l >>= 1, r >>= 1) {
			if(l % 2 == 1) {
				l2 = f.apply(l2, (T) data[l++]);
			}
			if(r % 2 == 1) {
				r2 = f.apply((T) data[--r], r2);
			}
		}
		return f.apply(l2, r2);
	}
	/**
	 * 全体の二項演算結果を返す
	 * @return 全体を二項演算した結果
	 */
	@SuppressWarnings("unchecked")
	public final T all(){ return (T) data[1]; }
	/**
	 * k番目の要素に作用素xを適用する
	 * @param k
	 * @param x
	 */
	@SuppressWarnings("unchecked")
	public final void apply(int k, final U x) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		data[k] = map.apply((T) data[k], x);
		for(int i = 0; ++i <= h;) {
			update(k >> i);
		}
	}
	/**
	 * 半開区間[l, r)について作用素xを適用する
	 * @param l
	 * @param r
	 * @param x
	 */
	public final void apply(int l, int r, final U x) {
		if(l >= r) {
			return;
		}
		l += sz;
		r += sz;
		for(int i = h; i > 0; i--) {
			if(((l >> i) << i) != l) {
				propagate(l >> i);
			}
			if(((r >> i) << i) != r) {
				propagate((r - 1) >> i);
			}
		}
		int l2 = l, r2 = r;
		for(; l < r; l >>= 1, r >>= 1) {
			if(l % 2 == 1) {
				allApply(l++, x);
			}
			if(r % 2 == 1) {
				allApply(--r, x);
			}
		}
		l = l2;
		r = r2;
		for(int i = 0; ++i <= h;) {
			if(((l >> i) << i) != l) {
				update(l >> i);
			}
			if(((r >> i) << i) != r) {
				update((r - 1) >> i);
			}
		}
	}
	/**
	 * 半開区間[l, x)がfnを満たす最初の要素位置xを返す
	 * @param l
	 * @param fn
	 * @return 半開区間[l, x)がfnを満たす最初の要素位置x
	 * if non-existence: n
	 */
	@SuppressWarnings("unchecked")
	public final int findFirst(int l, final Predicate<T> fn) {
		if(l >= n) {
			return n;
		}
		l += sz;
		for(int i = h; i > 0; i--) {
			propagate(l >> i);
		}
		T sum = e;
		do {
			while((l & 1) == 0) {
				l >>= 1;
			}
			if(fn.test(f.apply(sum, (T) data[l]))) {
				while(l < sz) {
					propagate(l);
					l <<= 1;
					final T nxt = f.apply(sum, (T) data[l]);
					if(!fn.test(nxt)) {
						sum = nxt;
						l++;
					}
				}
				return l + 1 - sz;
			}
			sum = f.apply(sum, (T) data[l++]);
		} while((l & -l) != l);
		return n;
	}
	/**
	 * 半開区間[x, r)がfnを満たす最後の要素位置xを返す
	 * @param r
	 * @param fn
	 * @return 半開区間[x, r)がfnを満たす最後の要素位置x
	 * if non-existence: −1
	 */
	@SuppressWarnings("unchecked")
	public final int findLast(int r, final Predicate<T> fn) {
		if(r <= 0) {
			return -1;
		}
		r += sz;
		for(int i = h; i > 0; i--) {
			propagate((r - 1) >> i);
		}
		T sum = e;
		do {
			r--;
			while(r > 1 && r % 2 == 1) {
				r >>= 1;
			}
			if(fn.test(f.apply((T) data[r], sum))) {
				while(r < sz) {
					propagate(r);
					r = (r << 1) + 1;
					final T nxt = f.apply((T) data[r], sum);
					if(!fn.test(nxt)) {
						sum = nxt;
						r--;
					}
				}
				return r - sz;
			}
			sum = f.apply((T) data[r], sum);
		} while((r & -r) != r);
		return -1;
	}
	/**
	 * 要素をリセットする
	 */
	public final void clear(){ Arrays.fill(data, e); }
	/**
	 * LazySegmentTreeを配列に変換したものを返す
	 * @return LazySegmentTreeの配列
	 */
	@SuppressWarnings("unchecked")
	public final T[] toArray(){ return (T[]) IntStream.range(0, n).mapToObj(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < n;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}
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/lazysegmenttree/LazySegmentTree.java
Back to top page