M_sea

HDU4630 No Pain No Game
HDUVjudge给出一个长为 $n$ 的序列,有 $m$ 个询问,每次询问 $\max\big\{\gcd(a_...
扫描右侧二维码阅读全文
23
2019/05

HDU4630 No Pain No Game

HDU

Vjudge

给出一个长为 $n$ 的序列,有 $m$ 个询问,每次询问 $\max\big\{\gcd(a_x,a_y)\big\}\ (x,y\in[l,r])$ 。

$1\leq n,m\leq 50000$ ,多组数据。

分析

奇妙的线段树姿势...

把所有询问离线,按右端点排序。

设 $pre[d]$ 表示上一个含有因子 $d$ 的数的位置,初始值赋为 $-1$ 。

然后用一棵线段树来维护区间最大值。线段树初始值为 $0$ 。

从左往右扫整个序列,假设当前扫到了 $x$ 。枚举 $x$ 的所有约数 $d$ ,然后如果 $pre[d]\neq -1$ ,就执行 modify(1,1,n,pre[d],d) 。这里的 modify 表示单点修改最大值。

枚举完所有约数后,考虑所有右端点在当前位置的询问 $(l,r)$ ,该询问的答案即为 query(1,1,n,l,r) 。这里的 query 指查询区间最大值。

感觉还是比较容易理解的。

另外题目没说值域,经过试验不超过 $50000$ 。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
    int mx[N<<2];

    inline void pushup(int o) { mx[o]=max(mx[ls],mx[rs]); }
    inline void modify(int o,int l,int r,int p,int w) {
        if (l==r) { mx[o]=max(mx[o],w); return; }
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls,l,mid,p,w);
        else modify(rs,mid+1,r,p,w);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return mx[o];
        int mid=(l+r)>>1,res=0;
        if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
        if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
        return res;
    }
} T;

struct query { int l,r,id; } q[N];
bool operator <(query a,query b) { return a.r<b.r; }

vector<int> fac[N];
int a[N],pre[N],ans[N];

int main() {
    for (re int i=1;i<N;++i)
        for (re int j=i;j<N;j+=i)
            fac[j].push_back(i);
    int Cases=read();
    while (Cases--) {
        memset(pre,-1,sizeof(pre)),memset(T.mx,0,sizeof(T.mx));
        int n=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        int m=read();
        for (re int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
        sort(q+1,q+m+1);
        for (re int i=1,j=1;i<=n&&j<=m;++i) {
            for (re int k=0;k<fac[a[i]].size();++k) {
                int d=fac[a[i]][k];
                if (pre[d]!=-1) T.modify(1,1,n,pre[d],d);
                pre[d]=i;
            }
            while (j<=m&&q[j].r==i) {
                ans[q[j].id]=T.query(1,1,n,q[j].l,q[j].r);
                ++j;
            }
        }
        for (re int i=1;i<=m;++i) printf("%d\n",ans[i]);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 13 PM

2 条评论

  1. xgzc

    我赌一包辣条,你绝对没有试验(

    1. M_sea

发表评论