题目描述
给定一个长为 \(n\) 的序列 \(a_1,\ldots,a_n\)，其中对于任意的 \(i\) 满足 \(1 \leq a_i \leq n\)。
定义一个二元组函数如下：
\[f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r) \]你需要回答 \(q\) 次询问，每次给定 \((l_i,r_i)\)，问其最少经过多少次 \(f\) 的调用（即 \((l,r) \rightarrow f((l,r))\)）使得 \((l_i,r_i)\) 变成 \((1,n)\)，若无解请输出 -1。
题解
智慧的性质题
首先注意到\(f((l,r))=\bigcup_{i=l}^{r-1}f((i,i+1))\)
发现可以推广到\(f^k((l,r))=\bigcup_{i=l}^{r-1}f^k((i,i+1))\)，可以用归纳法证明
接下来的做法就容易可以想出了
设\(F_{i,j}=f^{2^i}((j,j+1))\)，然后倍增解决，合并区间可以用线段树
\(\text{code}\)
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=1e5+100,B=40;
int n,q,a[N+10];
struct seg
{
int l,r;
}f[B+10][N+10];
int g[B+10][N+10];
seg merge(seg a,seg b){return (seg){min(a.l,b.l),max(a.r,b.r)};}
struct SEG
{
seg t[N<<2|1];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
void build(seg *f,int p=1,int l=1,int r=n-1)
{
if(l==r)
{
t[p]=f[l];
return;
}
build(f,ls,l,mid),build(f,rs,mid+1,r);
t[p]=merge(t[ls],t[rs]);
}
seg query(int L,int R,int p=1,int l=1,int r=n-1)
{
if(L<=l&&r<=R) return t[p];
if(R<=mid) return query(L,R,ls,l,mid);
else if(L>mid) return query(L,R,rs,mid+1,r);
else return merge(query(L,R,ls,l,mid),query(L,R,rs,mid+1,r));
}
#undef ls
#undef rs
#undef mid
}t[B+10];
int main()
{
// freopen("a.in","r",stdin);
read(n),read(q);
if(n==1)
{
for(;q--;) printf("0\n");
return 0;
}
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<n;i++) f[0][i]=(seg){min(a[i],a[i+1]),max(a[i],a[i+1])},g[0][i]=a[i];
t[0].build(f[0]);
for(int j=1;j<=B;j++)
{
for(int i=1;i<n;i++)
{
if(f[j-1][i].l==f[j-1][i].r) f[j][i]=(seg){g[j-1][f[j-1][i].l],g[j-1][f[j-1][i].l]};
else f[j][i]=t[j-1].query(f[j-1][i].l,f[j-1][i].r-1);
}
t[j].build(f[j]);
for(int i=1;i<=n;i++) g[j][i]=g[j-1][g[j-1][i]];
}
for(int l,r;q--;)
{
read(l),read(r);
if(l==1&&r==n)
{
printf("0\n");
continue;
}
ll ans=0;
if(l!=r)
for(int i=B;i>=0;i--)
{
seg tmp=t[i].query(l,r-1);
if(tmp.l!=1||tmp.r!=n)
{
l=tmp.l,r=tmp.r;
ans+=(1ll<<i);
}
if(l==r) break;
}
if(l==r) printf("-1\n");
else
{
seg tmp=t[0].query(l,r-1);
if(tmp.l==1&&tmp.r==n) printf("%lld\n",ans+1);
else printf("-1\n");
}
}
return 0;
}