Codeforces 301D (182 D) Yaroslav and Divisors

問題

1以上n以下のn個の整数a[i]が与えられる。
a[i]は全て互いに異なる。

このa[i]に対して、m個の以下のクエリに答えよ。
整数l, rが与えられる。
l≦i, j≦rなるi, jで、a[i]がa[j]の倍数であるものの個数を求める。

制約条件

n≦200000
クエリの個数≦200000

方針

ペアの個数は最大で、
n + n / 2 + n /3 + ... なのでO(nlogn)程度。具体的には250万個以下。
a[i]がa[j]の倍数であるような(i, j)を平面上に点として取ると、クエリは、
x座標、y座標がともにl以上r以下の点の個数を求めよと言っていることになる。

(i, j)をi≦jとしておけば、
x座標がl以上y座標がr以下の点の個数を求めればよくなる。
これは、よくある問題で、クエリをソートして、点をうちながら
bitを使ってx座標がr以下の点を数えるようにすれば点の個数Nに対してO(NlogN)でできる。

ソースコード

const int MX = 2500000;
int bit[MX];
inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}
inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}

int n, m, a[200000], ans[200000];
int pos[200001];

int main(){
	scanf("%d%d", &n, &m);
	rep(i, n) scanf("%d", a + i), pos[a[i]] = i;
	vector<pi> ps;
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j += i){
			int a = pos[i], b = pos[j];
			if(a > b) swap(a, b);
			ps.pb(mp(a, b));
		}
	}
	
	vector<pair<pi, int> > v;
	rep(i, m){
		int l, r;
		scanf("%d%d", &l, &r);
		v.pb(mp(mp(l - 1, r - 1), i));
	}
	sort(all(v));
	sort(all(ps));
	
	for(int i = m - 1, j = ps.size() - 1; i >= 0; i--){
		while(j >= 0 && ps[j].first >= v[i].first.first){
			add(ps[j].second + 1, 1);
			j--;
		}
		ans[v[i].second] = sum(v[i].first.second + 1);
	}
	rep(i, m) printf("%d\n", ans[i]);
	
	return 0;
}