题解：CF1707E Replace - 洛谷保存站

# [Replace](https://www.luogu.com.cn/problem/CF1707E)

[更好的阅读体验](https://www.cnblogs.com/wingheart/p/18470792)

## 题意

给你一个长度为 $n$ 的序列 $A$，有 $q$ 次询问，每次询问对于一个区间 $[l,r]$ 需要操作多少次才能变成区间 $[1,n]$，无解输出 $-1$。其中一次操作指原区间变成 $[l'=\min_{i=l}^r\{a_i\},r'=\max_{i=l}^r\{a_i\}]$。

## solution

看了[feecle大佬的题解](https://www.luogu.com.cn/article/w843rqy5)后对其中的结论有也许是另一种理解方式。

答案非严格上界是 $n^2$。因为如果你变换到了已经出现过的 $[l,r]$，就是无解。

首先题目的操作与取 $\min,\max$ 有关，因此通过丰富的经验和敏锐的观察力~~显然我没有~~可以发现：

$$f(l,r)=\cup_{i=l}^{r-1} f(i,i+1)$$

证明（或者应该叫理解方式）：对于每个 $i$，设 $a_x=\min(a_i,a_{i+1}),a_y=\max(a_i,a_{i+1})$，$f(i,i+1)$ 对应区间 $[a_x,a_y]$，其中相邻的 $i$ 对应区间至少有一个端点重合。因此所有的 $f(i,i+1)$ 并成连续的一段区间，其中最左的一个端点和最右的一个端点就是 $f(l,r)$ 的两端。可见等式是成立的。

蒟蒻的我不能直接观察出推论，但是也许可以这么想：我们考虑对所有 $f(i,i+1)$ 再进行一次操作，看看会发生什么。$f(i,i+1)$ 是若干段首尾相接的区间。每个区间会变成区间最小值和最大值为端点的新区间。由于区间是首尾相接的，因此新区间要么首尾相接要么相交得更多，而所有新区间的最左端点和最右端点一定等于所有区间的最小值和最大值，因此对这些 $f(i,i+1)$ 再进行一次操作，得到的区间 $=f^2(l,r)$。

以此类推，可以得到 $f^k(l,r)=\cup_{i=l}^{r-1} f^k(i,i+1)$。

所以我们不需要求所有的 $f(l,r)$，只需要求所有的 $f^k(i,i+1)$。然后是 RMQ 问题求区间最小值和最大值，ST 表即可。

因为 $f(1,n)=[1,n]$，所以显然操作 $k$ 次能否得到区间 $[1,n]$ 的 $k$ 满足单调性，$k$ 越大越容易得到指定区间。

因此考虑倍增。先求所有 $f^{2^0}(i,i+1)$，然后求所有 $f^{2^1}(i,i+1)$，以此类推，每一层都要做一次 RMQ。时间和空间都是 $O(n \log^2 n)$。

对每个询问，倍增，每次计算 RMQ 判断是否可以得到区间 $[1,n]$ 即可。时间复杂度 $O(q \log n)$。

总时间复杂度是 $O(n \log^2 n+q \log n)$。

据说猫树可以单 $\log$？感觉不会啊，会的大佬欢迎分享。

------------

update 2025.08.27：感谢 @fjy666 的 [Hack](https://www.luogu.com.cn/discuss/1142741)。错误原因是函数 `_cal()` 里对长度为 $1$ 的区间处理不正确。

长度为 $1$ 的区间是没有用的。

- 因为 $f(i,i)$ 得到的区间长度也是 $1$，无法得到 $[1,n]$。
- 若求 $f(l,r)$ 时存在 $l \le i < r$，$f(i,i+1)$ 的长度为 $1$，则 $f(i,i+1)$ 可以被 $f(i-1,i),f(i+1,i+2)$ 覆盖。

综上，我们可以不考虑长度为 $1$ 的区间。

由于区间 $[N,0]$ 在取 $\min,\max$ 的时候一定没有贡献，所以可以写成：

```cpp
constexpr pii del = {N,0};
if(x.fi==x.se || x==del) return del;
```

（Hack 前写的是 `if(x.fi==x.se) return x;`）

顺带将 $lg$ 加了 $1$ 以免出错。

仍然不知道怎么单 $\log$ 做，管它呢。

看了别的题解，使用线段树代替 ST 表做 RMQ 可以做到空间单 $\log$。至于猫树时间单 $\log$，忘记是谁说的了，感觉并不是单 $\log$？/kel

## code

如果你对 ST 表比较熟悉，代码不算难写。

```cpp
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int N=1e5+7;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
	x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) ;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
void write(T x,char ch) {
	static int st[20];
	int top=0;
	do {
		st[top++]=x%10;
		x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
	putchar(ch);
}
int n,q;
int a[N];
int l,r;
typedef pair<int,int> pii;
constexpr pii del = {N,0};
#define fi first
#define se second
pii st[50][25][N];
pii cal(pii a,pii b) { return {min(a.fi,b.fi),max(a.se,b.se)}; }
pii _cal(int p,pii x) {
	if(x.fi==x.se || x==del) return del;
	int lg=__lg(x.se-x.fi);
	return cal(st[p][lg][x.fi],st[p][lg][x.se-(1<<lg)]);
}
#define mp make_pair
int main() {
	read(n),read(q);
	rep(i,1,n) read(a[i]);
	rep(i,1,n-1) st[0][0][i]={min(a[i],a[i+1]),max(a[i],a[i+1])};
	int lg=__lg(n);
	++lg;
	rep(k,1,lg) for(int i=1;i+(1<<k)-1<=n-1;i++) st[0][k][i]=cal(st[0][k-1][i],st[0][k-1][i+(1<<(k-1))]);
	rep(p,1,lg<<1) {
		rep(i,1,n-1) st[p][0][i]=_cal(p-1,st[p-1][0][i]);
		rep(k,1,lg) for(int i=1;i+(1<<k)-1<=n-1;i++) st[p][k][i]=cal(st[p][k-1][i],st[p][k-1][i+(1<<(k-1))]);
	}
	rep(i,1,q) {
		read(l),read(r);
		if(l==1&&r==n) {
			puts("0");
			continue;
		}
		if(l==r) {
			puts("-1");
			continue;
		}
		pii y={l,r};
		int cnt=0;
		per(p,lg<<1,0) {
			pii x=_cal(p,y);
			if(x!=mp(1,n)) y=x,cnt+=(1<<p);
		}
		if(y!=mp(1,n)) y=_cal(0,y),cnt++;
		if(y==mp(1,n)) write(cnt,'\n');
		else puts("-1");
	}
}
```

正在渲染内容...