Codeforces #182 Div1 D. Yaroslav and Divisors

これもDiv1Dの中では正答者が多く、難易度が低い問題。
http://codeforces.com/contest/301/problem/D

問題

1～Nのpermutationである数列P[i]が与えられる。

ここでL[x],R[x]からなるクエリがQ個与えられる。
各クエリについて、L[x]≦q,w≦R[x]であり、かつP[w]がP[q]で割り切れるような(q,w)を答えよ。

解法

BITを使い、約数の数を管理する。
P[i]を左端から処理し、P[j]とP[i] (j

int N,M;
int A[200005],rev[200005];
vector<int> P[200005];
int L[200005],R[200005],ret[200005],num[200005];
vector<int> Q[200005];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,18> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i],rev[A[i]]=i;
	FOR(i,N) {
		for(j=A[i];j<=N;j+=A[i]) {
			if(rev[j]<=i) P[i].push_back(rev[j]);
			else P[rev[j]].push_back(i);
		}
	}
	
	FOR(i,M) {
		cin>>L[i]>>R[i];
		Q[R[i]-1].push_back(i);
	}
	
	FOR(i,N) {
		ITR(it,P[i]) bt.update(*it+1,1);
		FOR(j,Q[i].size()) ret[Q[i][j]]=bt.total((1<<18)-1)-bt.total(L[Q[i][j]]-1);
	}
	FOR(i,M) cout << ret[i] << endl;
}

まとめ

これはCでも良いぐらい簡単だったね。