CF1707E Replace 做题记录

给定一个长 $n$ 的序列 $a$，满足 $1 \leq a_i \leq n$。

定义函数 $f([l,r])=\left[\min\limits_{i=l}^r a_i,\max\limits_{i=l}^r a_i\right]$，$q$ 次询问，每次给定一个区间 $[l_i,r_i]$，求最少执行多少次变换 $[l,r] \rightarrow f([l,r])$ 使得 $[l_i,r_i]$ 变成 $[1,n]$，若无法变为 $[1,n]$ 则输出 -1。

$1\le n,q\le 10^5$。

十分智慧地，有一个结论：

对于两个有交的区间 $[x,y],[l,r]$，$f([x,y]\cup[l,r])=f([x,y])\cup f([l,r])$。

证明如下：

• 若 $[x,y]\cup[l,r]$ 内最大最小值同时在 $[x,y]$ 或 $[l,r]$ 中，则结论显然成立；
• 若最大值在一边而最小值在另一边，由于 $a_{[x,y]}\in f([x,y])$ 且 $a_{[l,r]}\in f([l,r])$，则 $a_{[l,r]\cap[x,y]}\in f([x,y])$ 且这一段也在 $f([l,r])$ 中，那么 $f([x,y])$ 和 $f([l,r])$ 一定有交，那么结论显然成立。

根据证明，$f([x,y])$ 和 $f([l,r])$ 也是有交的。

那么设变换 $k$ 次的函数为 $f^k$，则对于两个有交的区间 $[x,y],[l,r]$，有结论 $f^k([x,y]\cup[l,r])=f^k([x,y])\cup f^k([l,r])$。

那么不妨把区间拆成若干个 $[i,i+1]$，则 $f^{k}([l,r])=f^{k}([l,l+1])\cup f^{k}([l+1,l+2])\cup\dots\cup f^{k}([r-1,r])$。

那么倍增 $O(n\log ^2n)$ 预处理出 $f^{2^k}([i,i+1])$ 即可 $O(q\log n)$ 回答询问。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

typedef long long ll;

const int S=100005,BS=17,inf=1e8;

int n,q,a[S],mlog[S];
int mn[BS*2+1][BS+1][S],mx[BS*2+1][BS+1][S];

inline void initst(int id)
{
	for(int j=1;j<=mlog[n];j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			mn[id][j][i]=min(mn[id][j-1][i],mn[id][j-1][i+(1<<j-1)]);
			mx[id][j][i]=max(mx[id][j-1][i],mx[id][j-1][i+(1<<j-1)]);
		}
	}
}

inline int quemn(int a[BS][S],int l,int r)
{
	if(l==1&&r==n-1) return 1;
	if(l>r) return inf;
	int k=mlog[r-l+1];
	return min(a[k][l],a[k][r-(1<<k)+1]);
}

inline int quemx(int a[BS][S],int l,int r)
{
	if(l==1&&r==n-1) return n;
	if(l>r) return -inf;
	int k=mlog[r-l+1];
	return max(a[k][l],a[k][r-(1<<k)+1]);
}

int main()
{
	read(n),read(q);
	for(int i=1;i<=n;i++) read(a[i]);
	mlog[0]=-1;
	for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1;
	for(int i=1;i<=n-1;i++)
	{
		mn[0][0][i]=min(a[i],a[i+1]);
		mx[0][0][i]=max(a[i],a[i+1]);
	}
	initst(0);
	for(int s=1;s<=mlog[n]*2;s++)
	{
		for(int i=1;i<=n-1;i++)
		{
			mn[s][0][i]=quemn(mn[s-1],mn[s-1][0][i],mx[s-1][0][i]-1);
			mx[s][0][i]=quemx(mx[s-1],mn[s-1][0][i],mx[s-1][0][i]-1);
		}
		initst(s);
	}
	while(q-->0)
	{
		int l,r;
		read(l),read(r);
		if(l==1&&r==n)
		{
			puts("0");
			continue;
		}
		ll ans=0;
		for(int i=mlog[n]*2;i>=0;i--)
		{
			int nl=quemn(mn[i],l,r-1),nr=quemx(mx[i],l,r-1);
			if(nl!=1||nr!=n) ans+=1ll<<i,l=nl,r=nr;
		}
		ans++;
		int nl=quemn(mn[0],l,r-1),nr=quemx(mx[0],l,r-1);
		l=nl,r=nr;
		if(l==1&&r==n) printf("%lld\n",ans);
		else puts("-1");
	}
	return 0;
}