P3889 的分块做法

· · 题解

来写一下这道题的 O(n\sqrt{n}) 分块做法，感谢 @chaotic 的想法。由于 n,m,a_i 同阶下面复杂度分析统称 n。

首先一次询问 [l,r] 会把序列划分为三段： [1,l-1],[l,r],[r+1,n]。其中 [r+1,n] 的做法与 [1,l-1] 类似，重点关注 [1,l-1]。

首先明确一次询问可以将序列划分为这种形状（某些部分可能不存在）。

由于是计算 \gcd 最大值，考虑对各部分之间的贡献取 \max 得到答案。

不过在此之前，还需要做一些准备工作，比如求出每个数的因数，这是 O(n\sqrt{n}) 的。

中散对左块

注意到散块的大小是 O(\sqrt{n}) 的，我们可以将这个拆成 O(\sqrt{n}) 个单点询问：对于一个前缀 [1,x]，有一个数 y 与其取 \gcd 得到的最大值。

我们把这个询问存在 x 处，离线下来做，这样一共会产生 O(n\sqrt{n}) 个询问。

最后我们从小到大枚举 x，并且枚举 a_x 的因数 d，这个枚举的总复杂度是 O(n\sqrt{n}) 的。在枚举 d 后，我们就把 d 的所有倍数存着的 ans 与 d 取 \max，表示这些倍数能有它这个 \gcd。不难发现我们只需要在每种 d 第一次出现的时候干这回事，均摊下来是 O(n\lg n) 的。

在枚举完 d 后，对于在 x 存着的询问直接查询即可。

中整对左块

首先预处理出每个块包含了哪些因数。这是 O(n\sqrt{n}) 的。并且，我们也把这个询问离线下来。

类似于上一个从小到大枚举 x，再枚举 a_x 的因数 d。接着再枚举 x 后面的所有块，如果这个块里有着这个因数 d 就将这个块的 ans 与 d 取 \max，不难发现每个 d 也是只有第一次做有用，所以一共做 O(n) 次，总共是 O(n\sqrt{n}) 的。查询的时候就把它询问的整块的 ans 的 \max 当答案就行了。

实现细节

注意到离线存询问总是存一段连续的区间，所以实际上并没有单点拆开的必要。

预处理每个块包含的因数可以用 bitset 而不是用 bool 数组存，这样会快一点。但是这道题本来也不卡常。

//Private Eye,dancing with the wind.
#include<bits/stdc++.h>
using namespace std;

#define MAXN 100005
const int block=317,maxn=100000;
int n,m,a[MAXN],b[MAXN],L[MAXN],R[MAXN];
vector<int> st[MAXN];
bitset<MAXN> ts[block+5];
inline void init()
{
    for(int i=1;i<=maxn;i++)
        for(int j=i;j<=maxn;j+=i)
            st[j].emplace_back(i);
    for(int i=1;i<=n;i++)
        for(int x:st[a[i]])
            ts[b[i]][x]=1;
}

struct query{
    int l,r,id;
    query(int l_,int r_,int id_):
        l(l_),r(r_),id(id_){}
};
vector<query> ql[MAXN],qL[MAXN],qr[MAXN],qR[MAXN];
int ans[MAXN],ans1[MAXN],ans2[MAXN];
bitset<MAXN> vis;
inline void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[a[i]])
        {
            for(int x:st[a[i]])
                if(!vis[x])
                {
                    vis[x]=1;
                    for(int y=x;y<=maxn;y+=x)
                        ans1[y]=max(ans1[y],x);
                    for(int j=b[i]+1;j<=b[n];j++)
                        if(ts[j][x]) ans2[j]=max(ans2[j],x);
                }
        }
        for(query x:ql[i])
            for(int j=x.l;j<=x.r;j++)
                ans[x.id]=max(ans[x.id],ans1[a[j]]);
        for(query x:qL[i])
            for(int j=x.l;j<=x.r;j++)
                ans[x.id]=max(ans[x.id],ans2[j]);
    }
    vis.reset();
    memset(ans1,0,sizeof(ans1));
    memset(ans2,0,sizeof(ans2));
    for(int i=n;i>=1;i--)
    {
        if(!vis[a[i]])
        {
            for(int x:st[a[i]])
                if(!vis[x])
                {
                    vis[x]=1;
                    for(int y=x;y<=maxn;y+=x)
                        ans1[y]=max(ans1[y],x);
                    for(int j=b[i]-1;j>=1;j--)
                        if(ts[j][x]) ans2[j]=max(ans2[j],x);
                }
        }
        for(query x:qr[i])
            for(int j=x.l;j<=x.r;j++)
                ans[x.id]=max(ans[x.id],ans1[a[j]]);
        for(query x:qR[i])
            for(int j=x.l;j<=x.r;j++)
                ans[x.id]=max(ans[x.id],ans2[j]);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=(i-1)/block+1;
    for(int i=1;i<=b[n];i++) L[i]=R[i-1]+1,R[i]=min(L[i]+block-1,n);
    init(),scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        if(b[l]==b[r])
        {
            ql[l-1].emplace_back(query(l,r,i));
            qr[r+1].emplace_back(query(l,r,i)); 
        }
        else
        {
            ql[l-1].emplace_back(query(l,R[b[l]],i));
            ql[l-1].emplace_back(query(L[b[r]],r,i));
            if(b[l]+1!=b[r]) qL[l-1].emplace_back(query(b[l]+1,b[r]-1,i));
            qr[r+1].emplace_back(query(l,R[b[l]],i));
            qr[r+1].emplace_back(query(L[b[r]],r,i));
            if(b[l]+1!=b[r]) qR[r+1].emplace_back(query(b[l]+1,b[r]-1,i));
        }
    }
    solve();
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}