【题解】P7333 [JRKSJ R1] JFCA

· · 题解

前言

考察二分和 \text{ST} 表的结合运用。

思路

既然说好了是劣弧，所以肯定只能在向左或者向右的 \dfrac{len}{2} 个点中寻找（貌似不说也是这么干）。

再看如何寻找最小长度，线性一个个查找肯定不现实，所以就考虑区间最大值如何去操作。

可以发现有一个性质，一个区间内，一旦一个端点被固定下之后，这个区间内的最大值会随着区间的扩大而非严格单调递增，那么就找到这个区间的单调性了，现在多了一个二分可以选择。

维护区间最大值，看数据范围，可以用 \text{ST} 表进行维护。

现在就有了一种做法，确定一个位置，然后向前向后分别二分进行查找。

时间复杂度为 O(n\log n) ，可以通过此题。

至于如何断环成链，可以想一想：因为我们是要从左面和右面查找，那么前面和后面我们应该是存储一个完整的链，而我们当前固定的点是在中间的，所以就开三倍空间，复制三次链。以中间一条链为基准，进行前面后面的查找。

坑点

二分的时候可能随手就写成了这种形式qwq。

    int l=i-len+1;
        int r=i;
        //或者是
        int l=i;
        int r=i+len-1;

其实这种想法是 \text{very} 错误的，以为我们要找到区间一定是不能包含 i 这个点的，因为一旦这样那么有时候会出现一个奇奇怪怪的错误，注意看题目（i\neq j）

而且 i+len-1 这种做法也是错误的，自己手膜一下发现根本不需要 +1-1 的操作。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
const int N=1e5+9;
const int M=23;
int Max[N*3][M+1];//a[i]的最大值 
//处理中间一个复制的环的时候向左右挪动可能会发生数组越界，
//所以直接三倍，只处理中间一环即可。
//当一个端点确定是，该区间扩展时，最大值非严格单调递增，用二分，+st表维护 
int Log[N];
int a[N],b[3*N];
int n;
int f[N];
int read()
{
    int f=1,x=0;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^'0');s=getchar();}
    return f*x;
} 
int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}
int RMQ(int l,int r)
{
    int k=Log[r-l+1];
    return max(Max[l][k],Max[r-(1ll<<k)+1][k]);
}
void prepare()
{
    for(int i=1;i<=n;i++)//每次二分最长为一个链，不需要处理过多 
        Log[i]=log2(i);
    for(int j=1;j<M;j++)
        for(int i=1;i+(1ll<<j)-1<=3*n;i++)
            Max[i][j]=max(Max[i][j-1],Max[i+(1ll<<(j-1))][j-1]);
}
void erfen()
{
    int len=n/2;
    for(int i=n+1;i<=n+n;i++)
    {
        int ans=0x3f3f3f3f;
        if(RMQ(i-len,i-1)>=b[i])// 找左边 |i-len+1-----i-1|//注意没有i！！！ 
        {
            int l=i-len;
            int r=i-1;//Wrong，最后不能有i这个位置 
            while(l<=r)
            {
                int mid=(l+r)>>1;
                int cal=RMQ(mid,i-1);
                //printf("l= %d , r= %d , mid= %d , cal= %d\n",l,r,mid,cal);
                if(cal>=b[i])//Wrong在这个范围内有，缩小范围 
                {
                    //std::cout<<"b[i]= "<<b[i]<<std::endl;
                    ans=min(ans,i-mid);
                    l=mid+1;
                }
                else r=mid-1;//扩大范围继续找 
            }
        }
        if(RMQ(i+1,i+len)>=b[i])// 找右边 |i+1------i+len-1|，不要包含i！！！ 
        {
            int l=i+1;
            int r=i+len;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                int cal=RMQ(i+1,mid);//Wrong 
                //printf("l= %d , r= %d , mid= %d , cal= %d\n",l,r,mid,cal);
                if(cal>=b[i])
                {
                    ans=min(ans,mid-i);
                    r=mid-1;
                }
                else l=mid+1; 
            }
        }
        if(ans!=0x3f3f3f3f)
            printf("%d ",ans);
        else printf("-1 ");
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        Max[i][0]=Max[i+n][0]=Max[i+n+n][0]=read();
    for(int i=1;i<=n;i++)
        b[i]=b[i+n]=b[i+n+n]=read();
    prepare();
    erfen();
    return 0;
}