题解 P7244 【章节划分】

C3H5ClO · 2021-01-09 16:10:26 · 题解

学考回来随便开了一个比赛，提供一个 O(n\sigma_0(a_i)) 的分治做法。

显然，答案必然是全局最大值的约数。那么我们枚举这个约数 x 。对每个 x ，求出将这个序列划分成若干段，每一段的最大值都是 x 的倍数，段数的最大值。满足这个段数 \ge k 的最大的 x 就是答案。

对于一个区间 l,r，考虑求出它能划分的最多段数 f(l,r) 。设区间最大值所在位置是 mid 。

如果 x|a_{mid} ，那么贪心地取这个最大值为新的一段， f(l,r)=f(l,mid-1)+1+f(mid+1,r) 。

否则，如果 l>1，l-1 这个位置一定是某一个祖先的 mid ， [l,r] 的最大值可以属于 l-1 所在区间。同理，如果 r<n，[l,r] 的最大值可以属于 r+1 所在区间。因此， f(l,r)=max([r<n]f(l,mid-1),[l>1]f(mid+1,r)) 。

显然，递归树是笛卡尔树的一部分，求一次 f(l,r) 的复杂度为 O(n) ，因此时间复杂度得证。

至于区间最大值位置的求法，可以建笛卡尔树也可以直接ST表。

代码有手就行

const int N=100005;
int n,k,a[N],st[N][20],lg[N];
inline int pushup(int x,int y){return a[x]>a[y]?x:y;}
inline int getmax(int l,int r)
{
    int d=lg[r-l+1];
    return pushup(st[l][d],st[r-(1<<d)+1][d]);
}
int solve(int l,int r,int d)
{
    if(l>r)return 0;
    int mid=getmax(l,r);
    if(a[mid]%d==0)return solve(l,mid-1,d)+1+solve(mid+1,r,d);
    int ans=0;
    if(l>1)chkmax(ans,solve(mid+1,r,d));
    if(r<n)chkmax(ans,solve(l,mid-1,d));
    return ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    For(i,2,n)lg[i]=lg[i>>1]+1;
    For(i,1,n)scanf("%d",a+i),st[i][0]=i;
    For(i,1,lg[n])
        For(j,1,n-(1<<i)+1)
            st[j][i]=pushup(st[j][i-1],st[j+(1<<i-1)][i-1]);
    int x=a[getmax(1,n)],sqx=sqrt(x);
    For(i,1,sqx)
        if(x%i==0&&solve(1,n,x/i)>=k)
        {
            printf("%d",x/i);
            return 0;
        }
    Rof(i,sqx-1,1)
        if(x%i==0&&solve(1,n,i)>=k)
        {
            printf("%d",i);
            return 0;
        }
}