CF1707E Replace

题意：给定一个序列 $a$，定义 $f(\{l,r\})=\{min(a_{l\dots r}),max(a_{l\dots r})\}$，$q$ 次给定 $l,r$，问 $\{l,r\}$ 经过多少次 $f$ 函数后会变为 $\{1,n\}$，或者报告不可能。$n,q\le {10}^5$，1.5s，1024 MB。

首先看这个多少次，也许可以想到倍增，但是当前的 $(l,r)$ 一共有 $O(n^2)$ 个，无法计算。

后面的表示可能不够严谨，可以认为 $f(l,r)$ 表示上面的函数，会返回一个区间。

下面给出一个结论：

$f(l,r)=f(l,l+1)\cup f(l+1,l+2)\cup \cdots \cup f(r-1,r)$。

证明：设右边的为 $g(l,r)$。首先证明 $g(l,r)\subseteq f(l,r)$。容易发现每一个的 $f(i,i+1)$ 都是 $\subseteq f(l,r)$ 的，所以 $g(l,r)\subseteq f(l,r)$。然后考虑证明 $f(l,r)\subseteq g(l,r)$。容易发现在最大值和最小值之间的区间，跨度是连续的，也就是每一个 $i\in [l,r]$ 都可以在这段区间中找到一个位置 $p$ 使得 $i\in f(p,p+1)$，那么 $f(l,r)\subseteq g(l,r)$。综上，$f(l,r)=g(l,r)$。

有了上面的结论，我们就可以发现只需要记录所有的 $f(l,l+1)$ 即可。

然后考虑倍增，记录所有的 $f^{2^i}(l,l+1)$ 的答案，那么当 $f^{2^i}$ 转向 $f^{2^{i+1}}$ 时，我们相当于是求 $f^{2^i}(f^{2^i}(\{l,l+1\}))$。里面一层的我们已经知道了，现在要求外面一层的，那么就需要把 $f^{2^i}(\{l,r\})$ 区间内部的所有区间都并起来，这个可以使用线段树 / ST 表实现，预处理时间复杂度 $O(n{\log }^{2}n)$。

现在开始询问。考虑如何判断 $\{l,r\}$可不可以变成 $\{1,n\}$。容易发现如果超过 $O(n^2)$ 个都还没有出现 $\{1,n\}$ 的话，肯定出现了循环节，但是一出现 $\{1,n\}$ 就一定一直是 $\{1,n\}$ 了（最开始是 $\{1,n\}$ 除外），既然没有出现 $\{1,n\}$，那么就不可能出现 $\{1,n\}$ 了。剩下的直接倍增查找即可，时间复杂度 $O(n{\log }^{2}n+q\log n)$（ST 表，空间复杂度 $O(n{\log }^{2}n)$）或者 $O((n+q){\log }^{2}n)$（线段树，空间复杂度 $O(n\log n)$）。

void prework(int id)
{
	for (int i = 2; i <= n; ++ i) lg[i] = lg[i >> 1] + 1;
	for (int j = 1; (1 << j) <= n; ++ j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++ i)
			st[id][i][j] = st[id][i][j - 1] | st[id][i + (1 << (j - 1))][j - 1];
}

Segment query(int id, int l, int r)
{
	if (l > r) return {};
	int k = lg[r - l + 1];
	return st[id][l][k] | st[id][r - (1 << k) + 1][k];
}

int main()
{
	std::cin >> n >> Q;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i < n; ++ i) pw[0][i] = {std::min(a[i], a[i + 1]), std::max(a[i], a[i + 1])};
	for (int k = 0; k < L - 1; ++ k)
	{
		for (int i = 1; i < n; ++ i) st[k][i][0] = pw[k][i];
		prework(k);
		for (int i = 1; i < n; ++ i)
			pw[k + 1][i] = query(k, pw[k][i].l, pw[k][i].r - 1);
	}
	int l, r;
	while (Q --)
	{
		scanf("%d %d", &l, &r);
		if (l == 1 && r == n) {
			puts("0");
			continue;
		}
		if (l == r) {
			puts("-1");
			continue;
		}
		if (query(L - 2, l, r - 1) != Segment(1, n)) {
			puts("-1");
			continue;
		}
		long long res = 0;
		Segment cur(l, r);
		for (int i = L - 2; ~i; -- i)
			if (query(i, cur.l, cur.r - 1) != Segment(1, n)) res |= 1LL << i, cur = query(i, cur.l, cur.r - 1);
		printf("%lld\n", res + 1);
	}
	return 0;
}