题解：P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

ltl0825 · 2025-02-21 19:04:16 · 题解

P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi 的题解

题目传送门

思路：

我们通过找规律加画图可以发现，对于当前的 a_x，从当前位置向左找和向右找连续一段 a_x 的倍数，分别记为 l 和 r，r-l+1 就是我们当前的答案。
怎么统计呢？
我们发现，从 l\sim x 和从 x\sim r 中的做大公约数一定为 a_x。
我们可以二分长度，从 x 向左的长度和向右的长度，而且发现它们满足单调性。
那么如何快速判断一段区间的最大公约数呢？
这一题序列是静态的，可以使用 ST 表来完成，每次快速的判断。
可是，这样的时间复杂度为 \Theta (n\log^2n)。
怎么办呢？
我们加一些特殊优化。
设当前的最大公约数为 g。

• 若g为 1 那么直接跳出（在往下做没意义）。
• 若 g<a_x 直接返回 0 (公约数只会变小不会变大）。
• 若 g>a_x 且 g\bmod a_x\ne 0 直接返回 0 。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000010];
int idx[1000010];
int cnt[1000010];
int name[1000010];
int ans[1000010];
int ST[1000010][21];
int lowbit(int x)
{
    return x&-x;
}
int lg[1000010];
bool check(int pos,int mid,int f)//pos：当前位置，mid：长度，f=0/1，向左/向右
{
    if(!f)
    {
        int p=pos-mid;
        int g=a[pos];//初始化成a[pos]
        int d=mid;
        for(;d;)
        {
            int k=lowbit(d);
            /*三种情况*/
            if(g == 1)
            {
                break;
            }
            if(g<a[pos])
            {
                return 0;
            }
            if(g>a[pos]&&g%a[pos]!=0)
            {
                return 0;
            }
            g=__gcd(g,ST[p][lg[k]]);//取gcd
            p+=k;
            d-=k;
        }
        return g==a[pos];
    }
    else//同理
    {
        int p=pos;
        int g=a[pos+mid];
        int d=mid;
        for(;d;)
        {
            int k=lowbit(d);
            if(g == 1)
            {
                break;
            }
            if(g<a[pos])
            {
                return 0;
            }
            if(g>a[pos]&&g%a[pos]!=0)
            {
                return 0;
            }
            g=__gcd(g,ST[p][lg[k]]);
            p+=k;
            d-=k;
        }
        return g==a[pos];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ST[i][0]=a[i];
    }
    lg[1]=0;
    for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i/2]+1;
    }
    for(int j=1;j<=lg[n];j++)//初始化ST表
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            ST[i][j] = __gcd(ST[i][j-1],ST[i+((1<<(j-1)))][j-1]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int l=1,r=i-1;
        int anss=0;
        while(l<=r)//二分
        {
            int mid=(l+r)/2;
            if(check(i,mid,0))
            {
                anss=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        int anss1=0;
        l=1,r=n-i;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(i,mid,1))
            {
                anss1=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        cout<<anss+anss1+1<<' ';//左+右+自己
    }
    return 0;
}