TSG LIVE! 4 プログラミングコンテスト : F : LCM Interval

解法としては定番の組み合わせかな。
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval

問題

N要素の正整数列Aが与えられる。
このうちの区間で、LCMがX以下となる最長のものを求めよ。

解法

まず、区間のLCMはSegTreeを構築してO(logN)で求められるようにしておこう。
後は左端を総当たりし、LCMがXを超えない範囲で対応する右端を求めていく。
右端を求めるのに二分探索をしてしまうとO(Nlog^2 N)かかりTLに間に合わないが、右端は尺取り法で順次求めていくことにすると計算量がO(NlogN)で落ち着き間に合う。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1;
	V comp(V l,V r){
		if(l>=1LL<<30 || r>=1LL<<30) return max(l,r);
		return l/__gcd(l,r)*r;
	};
	
	SegTree_1(){val=vector<V>(NV*2,1);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 1;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; 
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

ll N,X;
ll A[501010];
SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) {
		cin>>A[i];
		st.update(i,A[i]);
	}
	
	int L=0,R=0;
	int CR=0;
	FOR(i,N) {
		if(CR<i) CR=i;
		while(CR<N && st.getval(i,CR+1)<=X) {
			CR++;
		}
		
		if(CR-i>R-L) {
			L=i;
			R=CR;
		}
	}
	cout<<(L+1)<<" "<<R<<endl;
}

まとめ

本番中微妙なバグで間に合わなかった。