## 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)$ .

3 2
1 2 3
1 3
2 3

2
0

## 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];
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