P3889 [GDOI2014] 吃

· · 题解

看到 n,m,V 都是 10^5 级别，应该马上反应过来：这个数据范围可以支持我们一些很暴力的操作。

考虑对 x \in [1,V]，预处理出 S_x 表示 x 的倍数在序列中出现位置的集合。令 d 代表 [1,V] 中所有数因子数的最大值，显然这部分预处理的时间复杂度与 \sum_{x}{\vert S_x \vert} 都是 O(nd) 级别的。

枚举 x，令 S_x ={p_1,p_2,\dots,p_k}，显然对于询问 [l,r]，答案可以取到 x 当且仅当：

发现第一个条件特别烦，又因为限制条件之间是或者的关系，考虑直接把条件拆开。换句话说，对所有询问，求出满足第一个条件前半部分与第二个条件的最大的 x，同理求出满足第一个条件后半部分与第二个条件的最大的 x，二者的 \max 就是该询问的答案。

显然拆出来的两部分对称，这里以满足第一个条件前半部分为例讲解。

不妨将上述条件转化为 O(nd) 个三元组 (x,y,z)，其含义为：所有满足 l < x,l \leq y \leq r 的询问的答案与 z 取 \max。将询问按 l 排序，三元组插入到 x+1 的位置，双指针枚举询问与三元组，不难发现需要实现的是单点修改与区间 \max 操作，用线段树可以实现。

于是问题得到解决，时间复杂度为 O(nd \log n)。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define mid ((tr[p].l+tr[p].r)>>1)
const int N=1e5+10;
int n,m,c,v[N],ans[N];
vector<int> d[N],pos[N];
vector<pair<int,int>> add[N];
struct Query
{
    int l,r,id;
}q[N];
struct node
{
    int l,r,mx;
}tr[N<<2];
inline void build(int p,int l,int r)
{
    tr[p].l=l;tr[p].r=r;tr[p].mx=0;
    if(l==r) return void();
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
inline void change(int p,int x,int w)
{
    if(tr[p].l==tr[p].r) return tr[p].mx=max(tr[p].mx,w),void();
    if(x<=mid) change(p<<1,x,w);else change(p<<1|1,x,w);
    tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
}
inline int query(int p,int l,int r)
{
    if(tr[p].l>=l&&tr[p].r<=r) return tr[p].mx;
    int res=0;
    if(l<=mid) res=max(res,query(p<<1,l,r));
    if(r>mid) res=max(res,query(p<<1|1,l,r));
    return res;
}
inline void solveL()
{
    for(int i=1;i<=n;i++) add[i].clear();
    for(int i=1;i<=m;i++) 
    {
        if(d[i].size()<2) continue;
        for(int j=1;j<(int)d[i].size();j++) add[d[i][0]+1].push_back(mp(d[i][j],i));
    }
    sort(q+1,q+c+1,[](Query A,Query B){return A.l<B.l;});
    build(1,1,n);
    for(int i=1,j=0;i<=c;i++)
    {
        while(j+1<=q[i].l)
        {
            ++j;
            for(auto x:add[j]) change(1,x.first,x.second);
        }
        ans[q[i].id]=max(ans[q[i].id],query(1,q[i].l,q[i].r));
    }
}
inline void solveR()
{
    for(int i=1;i<=n;i++) add[i].clear();
    for(int i=1;i<=m;i++) 
    {
        if(d[i].size()<2) continue;
        reverse(d[i].begin(),d[i].end());
        for(int j=1;j<(int)d[i].size();j++) add[d[i][0]-1].push_back(mp(d[i][j],i));
    }
    sort(q+1,q+c+1,[](Query A,Query B){return A.r>B.r;});
    build(1,1,n);
    for(int i=1,j=n+1;i<=c;i++)
    {
        while(j-1>=q[i].r)
        {
            --j;
            for(auto x:add[j]) change(1,x.first,x.second);
        }
        ans[q[i].id]=max(ans[q[i].id],query(1,q[i].l,q[i].r));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&v[i]);
        m=max(m,v[i]);pos[v[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j+=i)
            for(auto x:pos[j]) d[i].push_back(x);
    for(int i=1;i<=m;i++)
    {
        sort(d[i].begin(),d[i].end());
        d[i].erase(unique(d[i].begin(),d[i].end()),d[i].end());
    }
    scanf("%d",&c);
    for(int i=1;i<=c;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; 
    solveL();solveR();
    for(int i=1;i<=c;i++) printf("%d\n",ans[i]);
    return 0;
}