CF1707E Replace

对性质的观察，有点智慧。

题目的操作感觉就比较有传递性。容易得到：

$$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)$$

通过这一点直接倍增即可，并使用 ST 表维护，时间复杂度为 $\mathcal O(n\log ^2 n+q\log n)$。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,M=20,K=18;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,q;
int Log[N];
int L[M][M][N],R[M][M][N];
inline int qL(int t,int l,int r)
{
    int k=Log[r-l+1];
    return min(L[t][k][l],L[t][k][r-(1<<k)+1]);
}
inline int qR(int t,int l,int r)
{
    int k=Log[r-l+1];
    return max(R[t][k][l],R[t][k][r-(1<<k)+1]);
}
int main()
{
    read(n,q);
    for(int i=1,x;i<=n;i++)read(x),L[0][0][i]=R[0][0][i]=x;
    Log[0]=-1;
    for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int j=1;j<=K;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            L[0][j][i]=min(L[0][j-1][i],L[0][j-1][i+(1<<j-1)]);
            R[0][j][i]=max(R[0][j-1][i],R[0][j-1][i+(1<<j-1)]);
        }
    for(int t=1;t<=K;t++)
        for(int j=0;j<=Log[n];j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
            {
                L[t][j][i]=qL(t-1,L[t-1][j][i],R[t-1][j][i]);
                R[t][j][i]=qR(t-1,L[t-1][j][i],R[t-1][j][i]);
            }
    int l,r,ql,qr;
    while(q--)
    {
        read(l,r);
        if(l==1&&r==n){puts("0");continue;}
        int ans=1;
        for(int i=K;~i;i--)
        {
            ql=qL(i,l,r),qr=qR(i,l,r);
            if(ql>1||qr<n)l=ql,r=qr,ans+=1<<i;
        }
        ql=qL(0,l,r),qr=qR(0,l,r);
        if(ql>1||qr<n)puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}