HDOJ 4630 - No Pain No Game

#数据结构 #树状数组 #离线

Published on 2017-04-25

描述

给定一个 $1\sim n(n\le 50000)$ 的排列 $a_1, a_2, \ldots, a_n$ 。现在有 $q(q\le 50000)$ 次询问，每次询问区间 $[l, r]$ 内任选两个不同的数得到的 $\gcd$ 的最大值。

分析

区间 $\gcd$ 似乎没有什么好的办法，这个信息很难合并，所以一般序列上的做法是没有用的，我们得从题目的性质入手。

本题给定的是一个 $1\sim n$ 的排列，这意味着所有数的约数个数是 $O(n\ln n)$ 的。 $\gcd$ 是两个数的最大公约数，我们从约数方面下手。

离线询问，从右往左遍历序列。另外维护一个序列 $s$ ，我们希望遍历到 $i$ 的时候，区间 $[i, j]$ 的答案就是 $\max(s_i, s_{i + 1}, \ldots, s_j)$ 。

我们增量构造，假设 $i + 1$ 位置的 $s_i$ 已经构造正确了，现在我们要加入 $a_i$ 这个数。枚举 $a_i$ 的所有约数 $d$ ，找到 $\mathrm{lastPos}(d)$ 表示上一次包含约数 $d$ 的 $a_i$ 的位置，那么显然有 $d \mid \gcd(a_i, a_{\mathrm{lastPos}(d)})$ ，此时将 $s_{\mathrm{lastPos}(d)}$ 对 $d$ 取 $\max$ 。不难发现，这样我们就用所有的 $\gcd(a_i, a_j)$ 的更新了答案，而且由于我们是在 $\mathrm{lastPos}(d)$ 处更新的答案，所以在查询的时候不会漏掉任何答案。

使用树状数组实现单点取 $\max$ ，前缀最大值查询。 $\mathrm{lastPos}(d)$ 可以直接用一个数组维护，总的复杂度为 $O(n\log^2 n)$ 。

总结：本题的巧妙之处就在于 $1\sim n$ 的约数和是 $O(n\ln n)$ 级别的，所以我们可以对于每个 $i$ 都考虑所有的 $\gcd$ 的可能性，通过离线，我们只需要对每种可能性贪心地只考虑上一次出现的位置，这样就能将 $O(n^2)$ 对贡献降低到了 $O(n\ln n)$ 对贡献。

代码

//  Created by Sengxian on 2017/04/25.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  HDOJ 4630 离线 + 树状数组
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 50000 + 3, MAX_M = 50000 + 3;

struct Fenwick {
    #define lowbit(i) ((i) & -(i))

    int n, a[MAX_N];

    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof a);
    }

    void update(int pos, int val) {
        for (int i = pos + 1; i <= n; i += lowbit(i))
            a[i] = max(a[i], val);
    }

    int query(int pos) {
        int res = 0;
        for (int i = pos + 1; i > 0; i -= lowbit(i))
            res = max(res, a[i]);
        return res;
    }
} fen;

int n, m, a[MAX_N], pos[MAX_N], ans[MAX_M];

vector<pair<int, int> > querys[MAX_N];
vector<int> factors[MAX_N];

void solve() {
    fen.init(n);
    static int lastPos[MAX_N];
    memset(lastPos, -1, sizeof lastPos);
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < (int)factors[a[i]].size(); ++j) {
            if (lastPos[factors[a[i]][j]] != -1) fen.update(lastPos[factors[a[i]][j]], factors[a[i]][j]);
            lastPos[factors[a[i]][j]] = i;
        }
        for (int j = 0; j < (int)querys[i].size(); ++j)
            ans[querys[i][j].second] = fen.query(querys[i][j].first);
    }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    for (int i = 1; i < MAX_N; ++i)
        for (int j = i; j < MAX_N; j += i)
            factors[j].push_back(i);

    int caseNum = readInt();
    while (caseNum--) {
        n = readInt();
        for (int i = 0; i < n; ++i) a[i] = readInt(), pos[a[i]] = i, querys[i].clear();
        m = readInt();
        for (int i = 0; i < m; ++i) {
            int l = readInt() - 1, r = readInt() - 1;
            querys[l].push_back(make_pair(r, i));
        }

        solve();

        for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    }

    return 0;
}

BZOJ 4869 - [Shoi2017]相逢是问候 HDOJ 4626 - Jinkeloid

Sengxian's Blog

HDOJ 4630 - No Pain No Game

描述

分析

代码