【题解】 CF1237D 【Balanced Playlist】

· · 题解

题意

因为笔者太蒻了所以题意显得比较冗杂...

给定一个长度为 n 的数列 a_1,a_2,\cdots,a_n。

对于第 i 个数，我们按照 i,i+1,\cdots,n-1,n,1,\cdots,i-2,i-1,i,i+1,\cdots 这样进行循环遍历，停止遍历当且仅当前面的数均能被遍历且当前数严格小于已遍历数中的最大值的 \frac{1}{2} 。

换句话说，对于以第 i 个数开始的遍历，记在第 j 个数停止，则需满足条件：

我们需要求出从第 i 个整数，最长能遍历的长度为多少，若可以无限长，则输出 -1。

Solution

首先考虑遍历长度无限长的情况：既然是无限长，那么整个数列就会全部被遍历，也就是说数列中的最小值 a_{min} 满足 a_{min}\ge \dfrac{a_{max}}{2} ，而既然整个数列的最大值和最小值的都不会使其停止，那么从任意位置开始，其遍历长度均为无限长。

考虑更一般的情况：对于任意一个数，我们从这个数开始向右遍历，在遍历的过程中我们会维护一个 Max ，记录当前已被遍历的数中的最大值，在遍历过程中其状态的改变只有两种情况：

除了以上两种情况，其他节点对这个位置均无影响，那么我们应该怎么快速求出这两种情况的最靠前的位置呢？（肯定不会写O(n)暴力吧，如果暴力还优化什么。。。

显然这是一类 \text{RMQ} 问题，但又不同于正常的 \text{RMQ} 问题，我们求的是第一个满足某个条件的数，但又因为这个条件满足区间最大（最小）性质，所以我们可以考虑二分位置：

例如：当前我们需要在数列 11,5,3,7,2,13,1,9,6 中找到第一个大于 11 的位置，记二分左端点 l=1，右端点 r=9。

第一次二分：mid=(1+9)>>1=5 ，查询区间 [1,5] 中的最大值下标为 1，因为 a_1<=11 所以在区间 [1,5] 不存在大于 11 的数，l=mid+1=6

第二次二分： mid=(6+9)>>1=7 ，查询区间 [1,7] 中的最大值下标为 6，因为 a_6>11 ，所以在区间 [1,7] 中存在大于11的数，r=mid=7

第三次二分：mid=(6+7)>>1=6，查询区间 [1,6] 中的最大值下标为 6 ，因为 a_6>11 ，所以在区间 [1,6] 中存在大于11的数，r=mid=6

此时 l=r=6 ，找到第一个大于 11 的位置，单次期望复杂度O(logn)。

已经解决了怎么找到最近的满足条件的数，下面来考虑怎么转移：

若情况二靠前，则从该节点开始的答案显然为 ans_i=j-i 。

若情况一靠前，则从该节点开始的答案显然 ans_i=ans_j+j-i。

显然情况一的依赖关系不存在环，那记忆化搜索一遍就搞定了。

注意这道题是环，所以要破环为链。

Code

代码不压行，可读性较高

//压行课次
#include<bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;
const int MAXN=1e5+10;
int n,a[MAXN<<1],MX[MAXN<<1][19],MN[MAXN<<1][19],ans[MAXN],MXX,MNN=1e9;
int read(){int sss=0,fff=1;char ccc;ccc=getchar();while(ccc<'0'||ccc>'9'){if(ccc=='-')fff=-1;ccc=getchar();}while(ccc>='0'&&ccc<='9')sss=(sss<<1)+(sss<<3)+(ccc^'0'),ccc=getchar();return sss*fff;}
int MinST(int l,int r)
{
    int len=r-l+1;
    int k=log2(len);
    if(a[MN[l][k]]<a[MN[r-(1<<k)+1][k]]) return MN[l][k];
    return MN[r-(1<<k)+1][k];
}
int MaxST(int l,int r)
{
    int len=r-l+1;
    int k=log2(len);
    if(a[MX[l][k]]>a[MX[r-(1<<k)+1][k]]) return MX[l][k];
    return MX[r-(1<<k)+1][k];
}
int Min(int l,int r)
{
    int x=a[l-1];
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(a[MinST(l,mid)]*2>=x) l=mid+1;
        else r=mid;
    }
    return l;
}
int Max(int l,int r)
{
    int x=a[l-1];
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(a[MaxST(l,mid)]<x) l=mid+1;
        else r=mid;
    }
    return l;
}
int solve(int x)
{
    if(ans[x]) return ans[x];
    int A=Min(x+1,x+n),B=Max(x+1,x+n);
    if(A<B) return ans[x]=A-x;
    else return ans[x]=B-x+solve((B-1)%n+1);
}
int main()
{
//  freopen("123.in","r",stdin);
//  freopen("123.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=a[i+n]=read(),MX[i][0]=MN[i][0]=i,MX[i+n][0]=MN[i+n][0]=i+n,MXX=max(MXX,a[i]),MNN=min(MNN,a[i]);
    if(MNN*2>=MXX)
    {
        for(int j=1;j<=n;j++)
            printf("-1 ");
        return 0;
    }
    for(int k=1;k<=18;k++)
    {
        int len=1<<k;
        for(int i=1;i+len-1<=n*2;i++)
        {
            int j=i+len-1,mid=i+(len/2);

            if(a[MX[i][k-1]]<a[MX[mid][k-1]]) MX[i][k]=MX[mid][k-1];
            else MX[i][k]=MX[i][k-1];

            if(a[MN[i][k-1]]>a[MN[mid][k-1]]) MN[i][k]=MN[mid][k-1];
            else MN[i][k]=MN[i][k-1];
        }
    }
    for(int i=1;i<=n;i++)
        ans[i]=solve(i);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}