スライド区間最小値

目的

数列の区間[s,t)の最小値をO(1)で求めます。また、sまたはtの値を1増やす操作をO(1)で行います。

計算量

$O(1)$

使い方

void add(double v)
tを1増やす操作です。数列のインデックスtの値をvとしてください。
double min()
現在の区間の最小値をreturnします。
void poll()
sを1増やす操作です。

ソースコード

class SlideMin {
	int sz;
	ArrayDeque<Val> que = new ArrayDeque<>();

	void poll() {
		if (sz == 0)
			throw new AssertionError();
		--sz;
		--que.getFirst().sz;
		if (que.getFirst().sz == 0)
			que.pollFirst();
	}

	double min() {
		return que.getFirst().val;
	}

	void add(double v) {
		++sz;
		int cnt = 1;
		while (!que.isEmpty() && que.peekLast().val >= v) {
			cnt += que.peekLast().sz;
			que.pollLast();
		}
		que.addLast(new Val(v, cnt));
	}

	public class Val {
		double val;
		int sz;

		public Val(double val_, int sz_) {
			val = val_;
			sz = sz_;
		}
	}
}