D3 - Spare Table

template< class type >
class SpareTable {
	int ex[maxn + 1] {};
	bool vis[maxn + 1][log2maxn + 1] {};
	type f(int i, int k) {
		if (!vis[i][k]) {
			ar[i][k] = max(f(i, k - 1), f(i + (1 << (k - 1)), k - 1));
			vis[i][k] = true;
		}
		return ar[i][k];
	}
public:
	type ar[maxn + 1][log2maxn + 1] {};
	explicit SpareTable(const int n) {
		for (int i = 2; i <= n; i++) ex[i] = ex[i >> 1u] + 1;
		for (int i = 1; i <= n; i++) vis[i][0] = true;
	}
	type solve(int l, int r) {
		return max(f(l, ex[r - l]), f(r - (1 << ex[r - l]), ex[r - l]));
	}
};

SpareTable< int > st(maxn);