Codeforces #936 : Div2 F. Nobody is needed

ボス問の割には易しめ。
https://codeforces.com/contest/1946/problem/F

問題

1～NのPermutationである数列Aが与えられる。
以下のクエリに答えよ。

区間[L,R]が指定される。A[L...R]の部分列のうち、後の値が手前の値の倍数となっているものは何通りか。

解法

f(X,Y) := A[X...Y]の部分列のうち、問題文の条件を満たすもので、末尾にA[Y]を含むものが何通りか。

クエリに対しては、f(L,L)+f(L,L+1)+,....f(L,R)を答えればよい。
このfをBITで持って置く。初期状態では、X=0の場合を計算しておこう。
ここで、Xを増やしていきながら、BITのうちA[X]の倍数の現れる箇所を更新していけばよい。

int T,N,Q;
int A[1010101],re[1010101];
int L[1010101],R[1010101];
vector<int> ev[1010101];
ll ret[1010101];
ll M[1<<20];
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,21> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i+1];
			re[A[i+1]]=i+1;
			ev[i+1].clear();
			bt.add(i+1,-bt(i+1));
		}
		FOR(i,Q) {
			cin>>L[i]>>R[i];
			ev[L[i]].push_back(i);
		}
		for(i=1;i<=N;i++) {
			bt.add(re[i],1);
			ll sum=bt(re[i])-bt(re[i]-1);
			for(j=2*i;j<=N;j+=i) if(re[j]>re[i]) bt.add(re[j],sum);
		}
		for(i=1;i<=N;i++) {
			FORR(e,ev[i]) {
				ret[e]=bt(R[e])-bt(L[e]-1);
			}
			x=A[i];
			M[x]=bt(i)-bt(i-1);
			for(y=x;y<=N;y+=x) {
				ll del=M[y];
				M[y]=0;
				bt.add(re[y],-del);
				for(j=2*y;j<=N;j+=y) if(re[j]>re[y]) M[j]+=del;
			}
		}
		FOR(i,Q) cout<<ret[i]<<" ";
		cout<<endl;
	}
}

まとめ

計算量が心配だったけど、意外に行けるもんだい。