CF1707E Replace

题目描述

给定一个长为 $n$ 的序列 $a_1,\dots ,a_n$，其中对于任意的 $i$ 满足 $1\le a_i\le n$。

定义一个二元组函数如下：
f((l,r))=(min⁡{al,…,ar},max⁡{al,…,ar})(l≤r)f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)f((l,r))=(min{al​,…,ar​},max{al​,…,ar​})(l≤r)

你需要回答 $q$ 次询问，每次给定 $(l_i,r_i)$，问其最少经过多少次 $f$ 的调用（即 $(l,r)\to 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))$，然后倍增解决，合并区间可以用线段树，长度为$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;
}