http://acm.hdu.edu.cn/showproblem.php?pid=4630

比较能体现离线威力的一道题。
为了方便使用树状数组维护区间最值,我们从右往左遍历 a 数组,这样查询也要根据 l 从大往小排序。
对于 a[i] 这个数,对它的每个因子 m,我们找一个在 a[i] 右边的,离 a[i] 最近的,且同样有因子 m 的数,其下标为 j,则更新树状数组 j 位置的最值为 m。
为什么找最近的?因为离线查询按照 l 排序后有个天然的包含关系
然后用树状数组查询区间最值就行。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 531 ms, 1612 KB */
const int mx = 5e4 + 5;

struct Q {
    int l, r, id;
    bool operator < (const Q &b) const {
        return l > b.l;
    }
} q[mx];

int n;
int tree[mx];
void U(int pos, int val) {for (; pos <= n; pos += pos & -pos) Qmax(tree[pos], val);}
int get_max(int pos) {int ans = 0; for (; pos > 0; pos &= pos - 1) Qmax(ans, tree[pos]); return ans;}

int pos[mx];  // pos[i]:在当前状态下,含有因子 i 的最靠左的数的位置
int a[mx], ans[mx];

int main() {
    int m, i, j, k, cnt;
    TT {
        SI(n);
        SA(a + 1, n);
        SI(m);
        For(i, m) {
            SII(q[i].l, q[i].r), q[i].id = i;
        }
        sort(q, q + m);
        mem(tree, 0), mem(pos, 0);
        cnt = 0;
        rForr(i, n, 1) {
            for (j = 1; j * j <= a[i]; ++j) {
                if (a[i] % j) continue;
                if (pos[j]) U(pos[j], j);  // 更新 gcd(a[i], a[pos[j]]) 的最值为 j
                k = a[i] / j;
                if (k != j && pos[k]) U(pos[k], k);  // 更新 gcd(a[i], a[pos[j]]) 的最值为 k
                pos[j] = pos[k] = i;
            }
            while (cnt < m && q[cnt].l == i) {
                ans[q[cnt].id] = get_max(q[cnt].r);
                ++cnt;
            }
        }
        PAn(ans, m);
    }
    return 0;
}

Comments

comments powered by Disqus