The Preliminary Contest for ICPC Asia Xuzhou 2019 I query

Description:

Given a permutation pp of length $n$ , you are asked to answer mm queries, each query can be represented as a pair $(l ,r )$ , you need to find the number of pair $(i ,j)$ , such that $l \le i < j \le r$ and $\min(p_i,p_j) = \gcd(p_i,p_j )$ .

Input:

There is two integers $n(1 \le n \le 10^5)$ , $m(1 \le m \le 10^5)$ in the first line, denoting the length of pp and the number of queries.

In the second line, there is a permutation of length $n$ , denoting the given permutation $p$ . It is guaranteed that $p$ is a permutation of length $n$ .

For the next $m$ lines, each line contains two integer $l_i$ and $r_i(1 \le l_i \le r_i \le n)$ , denoting each query.

Output:

For each query, print a single line containing only one integer which denotes the number of pair $(i,j)$ .

Sample Input:

3 2
1 2 3
1 3
2 3

Sample Output:

2
0

题目链接

一个数列 $p_{i}(i \in [1,n])$ 是 $1 \sim n$ 的某个排列,$q$ 次询问每次查询区间 $i \in [l,r]$ 内 $\min(p_i,p_j)=\gcd(p_i,p_j)$ 的 $(i,j)$ 数对数量

预处理出 $nlogn$ 个数对并保存所有左右边界,离线所有询问并按照右端点升序排序

枚举右端点,用线段树维护更新合法的预处理过的数对左边界,对每个询问查询其左右边界之间的可行数对数量并记录

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
struct SegTree {
    int n;
    int tree[maxn * 4];
    void Pull(int o) {
        tree[o] = tree[o * 2] + tree[o * 2 + 1];
    }
    void Build(int o, int l, int r) {
        tree[o] = 0;
        if (l == r) return;
        int m = (l + r) / 2;
        Build(o * 2, l, m);
        Build(o * 2 + 1, m + 1, r);
        Pull(o);
    }
    void Init(int _n) {
        n = _n;
        Build(1, 1, n);
    }
    void Modify(int o, int l, int r, int idx) {
        if (l == r) {
            ++tree[o];
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) Modify(o * 2, l, m, idx);
        else Modify(o * 2 + 1, m + 1, r, idx);
        Pull(o);
    }
    void Modify(int idx) { Modify(1, 1, n, idx); }
    int Query(int o, int l, int r, int ll, int rr) {
        if (ll <= l && rr >= r) return tree[o];
        int m = (l + r) / 2, ret = 0;
        if (ll <= m) ret += Query(o * 2, l, m, ll, rr);
        if (rr > m) ret += Query(o * 2 + 1, m + 1, r, ll, rr);
        return ret;
    }
    int Query(int ll, int rr) { return Query(1, 1, n, ll, rr); }
};
int n, m;
int a[maxn], pos[maxn];
struct Query { int l, r, id; };
Query qry[maxm];
std::vector<int> add[maxn];
SegTree T;
int ans[maxm];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        pos[a[i]] = i;
    }
    for (int x = 1; x <= n; ++x) {
        for (int i = 1; i * i <= x; ++i) {
            if (x % i == 0) {
                if (i != x) add[std::max(pos[i], pos[x])].push_back(std::min(pos[i], pos[x]));
                if (i * i != x && x / i != x) add[std::max(pos[x / i], pos[x])].push_back(std::min(pos[x / i], pos[x]));
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        std::cin >> qry[i].l >> qry[i].r;
        qry[i].id = i;
    }
    std::sort(qry + 1, qry + m + 1, [&](Query k1, Query k2) { return k1.r < k2.r; });
    T.Init(n);
    int idx = 1;
    for (int i = 1; i <= n; ++i) {
        for (auto &l : add[i]) T.Modify(l);
        while (idx <= m && qry[idx].r == i) {
            ans[qry[idx].id] = T.Query(qry[idx].l, qry[idx].r);
            ++idx;
        }
    }
    for (int i = 1; i <= m; ++i) std::cout << ans[i] << '\n';
    return 0;
}
Last modification:September 7th, 2019 at 07:29 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment