Codeforces #830 : Div2 E. Location

うーむ、こういう力技系、なかなか戸惑う。
https://codeforces.com/contest/1732/problem/E

問題

N要素の整数列A,Bが与えられる。
以下のクエリに順次答えよ。

• A[L..R]に同じ値Xを代入する
• 区間[L,R]において、LCM(A[i],B[i])/GCD(A[i],B[i])の最小値を答える。

解法

平方分割で解く。
N要素を√N要素ずつのBucketに分け、

• あらかじめ、Bucket内の全A[i]が一致する場合のLCM(A[i],B[i])/GCD(A[i],B[i])の最小値を計算しておく
• 加えて、現在のLCM(A[i],B[i])/GCD(A[i],B[i])の最小値を保持しておく

max(A)やmax(B)がO(N)なので、前処理はO(N√N)で済む。
前者のクエリでは、更新するBucket数及びO(√N)だし、後者のクエリもO(√N)個のBucket及び要素を見ればよいので間に合う。

int N,Q;
int A[250*250+2],B[250*250+2];

const int DI=120;
int G[605][50500];
ll ans[605][50500];
int cov[50500];
ll ret[805];
vector<int> di[50500],pi[505050];

ll val(int a,int b) {
	int g=__gcd(a,b);
	return (ll)(a/g)*(b/g);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=50000;i++) {
		for(j=i;j<=50000;j+=i) {
			di[j].push_back(i);
		}
		if(i>1&&pi[i].empty()) {
			for(j=i;j<=50000;j+=i) {
				pi[j].push_back(i);
			}
		}
	}
	cin>>N>>Q;
	FOR(i,250*250) A[i]=B[i]=1;
	
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,50500/DI+2) {
		ret[i]=1LL<<60;
		FOR(j,50102) G[i][j]=1LL<<30;
	}
	FOR(i,50000+DI) {
		chmin(ret[i/DI],val(A[i],B[i]));
		FORR(a,di[B[i]]) chmin(G[i/DI][a],B[i]/a);
	}
	FOR(i,50500/DI+2) {
		for(j=1;j<=50000;j++) {
			ans[i][j]=(G[i][j]==1LL<<30)?(1LL<<60):G[i][j];
			FORR(p,pi[j]) if(ans[i][j/p]!=1LL<<60) chmin(ans[i][j],ans[i][j/p]*p);
		}
	}
	
	while(Q--) {
		int L,R,X;
		cin>>i>>L>>R;
		L--;
		if(i==1) {
			cin>>X;
			if(L/DI!=R/DI) {
				x=L/DI;
				if(cov[x]) {
					for(i=x*DI;i<x*DI+DI;i++) A[i]=cov[x];
					cov[x]=0;
				}
				for(i=L;i<x*DI+DI;i++) A[i]=X;
				ret[x]=1LL<<60;
				for(i=x*DI;i<x*DI+DI;i++) chmin(ret[x],val(A[i],B[i]));
				L=x*DI+DI;
			}
			while(L/DI!=R/DI) {
				x=L/DI;
				cov[x]=X;
				ret[x]=ans[x][X];
				L+=DI;
			}
			x=L/DI;
			if(cov[x]) {
				for(i=x*DI;i<x*DI+DI;i++) A[i]=cov[x];
				cov[x]=0;
			}
			for(i=L;i<R;i++) A[i]=X;
			ret[x]=1LL<<60;
			for(i=x*DI;i<x*DI+DI;i++) chmin(ret[x],val(A[i],B[i]));
		}
		else {
			ll pat=1LL<<60;
			if(L/DI!=R/DI) {
				x=L/DI;
				for(i=L;i<x*DI+DI;i++) chmin(pat,val(cov[x]?cov[x]:A[i],B[i]));
				L=x*DI+DI;
			}
			while(L/DI!=R/DI) {
				chmin(pat,ret[L/DI]);
				L+=DI;
			}
			x=L/DI;
			for(i=L;i<R;i++) chmin(pat,val(cov[x]?cov[x]:A[i],B[i]));
			cout<<pat<<endl;
		}
	}
	
}

まとめ

実装は難しくはないけどちょっとめんどいな。