2019icpc徐州网络赛I query (离线+树状数组)

题目链接
大意：给你一个数组，每次询问一个区间，问你区间 $l, r$ 内合法的 $(i, j)$ 有多少对。
若 $m i n (a_{i}, a_{j}) = g c d (a_{i}, a_{j})$ 则合法。
思路：离线处理。
先预处理出和每个i构成合法区间的所有j，我们用两个 $v e c t o r$ 来存，一个表示比他大的，一个表示比他小的（小的就是说v[i]里存的是和i匹配的所有位置，其 $i < j$ ，且 $a_{i} > a_{j}$ ,大的就是 $a_{i} > a_{j}$ ）
直接枚举倍数即可。
然后把所有合法位置加到树状数组中。
然后按询问的l从小到达排序，用一个指针记录当前的左端点，每次移动到当前询问的l，移动过程中在树状数组中删除<l的位置的贡献。每次查询答案就相当于查询前缀和，直接查即可。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
int n, m, a[N], pos[N];
struct uzi {
	int l, r, i;
	bool operator <(const uzi &t)const {
		return l < t.l;
	}
} p[N];
LL t[N];
void add(int p, int d) {
	for (int i = p; i <= n; i += (i & -i))t[i] += d;
}
LL ans[N];
LL get(int p) {
	LL ans = 0;
	for (int i = p; i; i -= (i & -i))ans += t[i];
	return ans;
}
vector<int>x[N], y[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]), pos[a[i]] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 2 * a[i]; j <= n; j += a[i]) {
			if (pos[j] > i)x[i].pb(pos[j]);
			else y[pos[j]].pb(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 2 * a[i]; j <= n; j += a[i]) {
			if (pos[j] > i)add(pos[j], 1);
			else add(i, 1);
		}
	}
	for (int i = 1; i <= m; i++)cin >> p[i].l >> p[i].r, p[i].i = i;
	int l = 1;
	sort(p + 1, p + 1 + m);
	for (int i = 1; i <= m; i++) {
		while (p[i].l > l) {
			for (auto k : x[l]) {
				add(k, -1);
			}
			for (auto k : y[l]) {
				add(k, -1);
			}
			l++;
		}
		ans[p[i].i] = get(p[i].r);
	}
	for (int i = 1; i <= m; i++) {
		printf("%lld\n", ans[i] );
	}
	return 0;
}