Codeforces #330 Div1 D. REQ

平方分割難しい。
http://codeforces.com/contest/594/problem/D

問題

N要素の整数列A[i]が与えられる。

この数列に対し、以下のクエリQ個に答えよ。
各クエリは区間L[i],R[i]で与えられる。
A[L[i]]～A[R[i]]の数値をかけた値に対し、オイラー関数を適用した値を答えよ。

解法

オイラー関数φ(x)は、xを素因数分解して現れる各素数p[i]に対し(1-1/p[i])を適宜掛けたものとなる。
A[L[i]]～A[R[i]]の数値を掛けるのは、累積積？を前処理で求めておけばO(1)で処理できる。
あとは区間に登場する各素因数について、1回だけ(1-1/p[i])を掛けていかなければならない。

A[i]の各素因数について、前及び後にある同じ素因数を持つ最寄のindexを求めておく。
こうすると区間が伸び縮みした際、ある素因数の有無が0個になるか1個以上になるかは容易に求められる。
後はQ個のクエリについて、クエリ毎の区間の伸び縮み量が小さくなるような順で処理すればよい。

これはCFで良く出る平方分割で、L[i]を√N程度毎に分割し、同じ区間に入るL[i]について、R[i]順にソートして処理すると良い。
そうするとO(Q+N√N)程度で処理できる。
ただ、この問題は分割数を丁寧に選ばないとTLEする。

int mo=1000000007;

const int prime_max = 1000001;
int NP,prime[100000],divp[prime_max],id[1010100];

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		id[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int N,Q;
int A[202020];
ll P[202020],PR[202020];
vector<int> di[202020];

int L[202020],R[202020],ret[202020];;

vector<pair<int,int> > pre[202020],nex[202020];
vector<pair<int,int> > QQ[2505];
int rev[1202020],revp[1202020];
int num[82020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	for(i=2;i<=1000000;i++) if(divp[i]==0) {
		rev[i]=(i-1)*1LL*modpow(i) % mo;
		revp[i]=modpow(rev[i]) % mo;
	}
	
	cin>>N;
	P[0]=PR[0]=1;
	FOR(i,N) {
		cin>>A[i];
		P[i+1]=P[i]*A[i]%mo;
		PR[i+1]=modpow(P[i+1]);
		x=A[i];
		while(divp[x]) di[i].push_back(divp[x]), x/=divp[x];
		if(x>1) di[i].push_back(x);
		sort(ALL(di[i]));
		di[i].erase(unique(ALL(di[i])),di[i].end());
	}
	
	ZERO(num);
	FOR(i,N) {
		FORR(r,di[i]) pre[i+1].push_back({num[id[r]],r}), num[id[r]]=i+1;
		sort(ALL(pre[i+1]));
	}
	FOR(i,NP+1) num[i]=N+1;
	for(i=N-1;i>=0;i--) {
		FORR(r,di[i]) nex[i+1].push_back({num[id[r]],r}), num[id[r]]=i+1;
		sort(ALL(nex[i+1]));
		reverse(ALL(nex[i+1]));
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		QQ[L[i]/450].push_back({R[i],i});
	}
	
	FOR(i,400) {
		ll pat=1;
		int LL=1,RR=0;
		sort(ALL(QQ[i]));
		FORR(r,QQ[i]) {
			x=r.first;
			y=r.second;
			
			while(RR<x) {
				RR++;
				FORR(rr,pre[RR]) {
					if(rr.first>=LL) break;
					(pat *= rev[rr.second])%=mo;
				}
			}
			while(LL<L[y]) {
				FORR(rr,nex[LL]) {
					if(rr.first<=RR) break;
					(pat *= revp[rr.second])%=mo;
				}
				LL++;
			}
			while(LL>L[y]) {
				LL--;
				FORR(rr,nex[LL]) {
					if(rr.first<=RR) break;
					(pat *= rev[rr.second])%=mo;
				}
			}
			ret[y]=P[RR]*PR[LL-1]%mo*pat%mo;
		}
	}
	FOR(i,Q) _P("%d\n",ret[i]);
	
}

まとめ

本番解けたと思ったら、TLEで残念。