hdu 4630 No Pain No Game（线段树离线处理）

短命女 2021-11-14 13:48 176阅读 0赞

## 题意：给出n个数，每个数的范围是1~n的。n<=50000；然后查询m次，m<=50000，每次查询\[l,r\]区间内，任意两个数（不能是同一个数）的gcd的最大值。 ##

## 分析：pre\[x\]表示因子x从前往后最近出现的位置，考虑位置i时，如果有因子x，则P\[x\]~i之间即可以有因子x，线段树维护区间最大值。将查询离线，按照右端点排序，一遍扫过去，一边更新，一边求值。也可以从后往前扫。（nt\[x\]表示因子x从后往前最近出现的位置） ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define lson(x) (x<<1)
    #define rson(x) ((x<<1)|1)
    const int N = 5e4+5;
    int lc[N<<2], rc[N<<2], s[N<<2];
    
    void pushup(int u) { s[u] = max(s[lson(u)], s[rson(u)]); }
    
    ///区间开[0,n] 取0错开区间左端点重合的情况
    void build(int u, int l, int r) {
        lc[u] = l, rc[u] = r, s[u] = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lson(u), l, mid);
        build(rson(u), mid+1 , r);
        pushup(u);
    }
    
    void modify(int u, int p, int v) {
        if (lc[u] == rc[u]) {
            s[u] = max(s[u], v);
            return;
        }
        int mid = (lc[u] + rc[u]) >> 1;
        if (p <= mid) modify(lson(u), p, v);
        else modify(rson(u), p, v);
        pushup(u);
    }
    
    int query(int u, int l, int r) {
        if (l <= lc[u] && rc[u] <= r)
            return s[u];
        int mid = (lc[u] + rc[u]) >> 1, ret = 0;
        if (l <= mid) ret = max(ret, query(lson(u), l, r));
        if (r > mid) ret = max(ret, query(rson(u), l, r));
        return ret;
    }
    
    struct nd {
        int l, r, id;
        nd(int l = 0, int r = 0, int id = 0):l(l), r(r), id(id) {}
        bool operator < (const nd& u) const { return r < u.r; }
    }q[N + 5];
    
    int n, m, a[N + 5], pre[N + 5], ans[N + 5];
    vector<int> yz[N + 5];
    ///预处理每个数的因子
    void init () {
        for (int i = 1; i <= N; i++)
            for (int j = i; j <= N; j += i)
                yz[j].push_back(i);
    }
    
    int main () {
        init();
        int cas;
        scanf("%d",&cas);
        while (cas--) {
            scanf("%d",&n);
            memset(pre, 0, sizeof(pre));
            for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
            scanf("%d",&m);
            for (int i = 0; i < m; i++) {
                scanf("%d%d", &q[i].l,&q[i].r);
                q[i].id = i;
            }
            sort(q, q + m);///将区间按右端点
            build(1, 0, n);
            int p = 0;
            for (int i = 1; i <= n; i++) {
                int u = a[i];
                for (int j = 0; j < yz[u].size(); j++) {
                    int v = yz[u][j];
                    modify(1, pre[v], v);///更新最近一段同时出现因子的区间的最大值
                    pre[v] = i;
                }
                while (p < m && q[p].r == i) {
                    ans[q[p].id] = query(1, q[p].l, q[p].r);
                    p++;
                }
            }
            for (int i = 0; i < m; i++)
                printf("%d\n", ans[i]);
        }
        return 0;
    }