Codeforces #271 Div2 F. Ant colony

本番だいぶ混乱したけど何とか正答。
http://codeforces.com/contest/474/problem/F

問題

N匹の蟻の強さはS[i]である。この時、以下のクエリT個に回答せよ。

• クエリはL[i], R[i]の２値で構成される。L[i]≦x≦R[i]である各xに対して、同じくL[i]≦y≦R[i]であるyのうち１つでもS[y]がS[x]で割り切れないものがある場合、x番目の蟻は食べられる。各クエリで食べられてしまう蟻の数を答えよ。

解法

各xに対し、a[x]<=x<=b[x]でかつS[a[x]]～S[b[x]]の間がすべてS[x]で割り切れるような最小のa[x]と最大のb[x]を求める。
これはS[i]の範囲の最大公約数を求めるSegmentTreeを用いて、a,bを二分探索することでO(N*(logN)^2)で求められる。

次に、クエリをR順でソートしたのち、蟻のidを0から順に処理していき、R[i]==蟻のidとなるようなクエリを適宜処理していく。
その際、先のa[x]・b[x]の値を用いてBITで「L[i]がこの範囲なら食べられる蟻の数がこうなる」という値を管理する。

今id番の蟻を処理しているとき、x＜idな蟻について以下のようになる。

• id≦b[x]なら、x番の蟻が食べられるのはクエリがa[x]未満までの幅を持つ(L[i]＜a[x])の場合
• b[x]＜idなら、x番の蟻が食べられるのはクエリがx番の蟻を含む(L[i]≦a[x])場合

あとは上記値をBITで管理すればよい。

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==def) return r;
		if(r==def) return l;
		return __gcd(l,r);
	};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		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]);
	}
};

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,20> bt;

int N,T;
ll S[100500],L[100500],R[100500];
int LP[100500],RP[100500];
SegTree_1<ll,1<<18> st;
int res[100001];
vector<int> del[100001];
vector<int> QQ[100001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i], st.update(i+1,S[i]);
	FOR(i,N) {
		LP[i]=RP[i]=i+1;
		for(j=18;j>=0;j--) {
			x=LP[i]-(1<<j);
			if(x>0 && st.getval(x,i+1)%S[i]==0) LP[i]=x;
			x=RP[i]+(1<<j);
			if(x<=N && st.getval(i+1,x+1)%S[i]==0) RP[i]=x;
		}
		LP[i]--;
		RP[i]--;
	}
	cin>>T;
	FOR(i,T) {
		cin>>L[i]>>R[i];
		L[i]--,R[i]--;
		QQ[R[i]].push_back(i);
	}
	
	FOR(i,N) {
		bt.update(LP[i],1);
		del[RP[i]].push_back(i);
		FOR(j,QQ[i].size()) res[QQ[i][j]]=bt.total(i+1)-bt.total(L[QQ[i][j]]);
		ITR(it,del[i]) bt.update(LP[*it],-1), bt.update(*it+1,1);
	}
	
	FOR(i,T) _P("%d\n",res[i]);
}

まとめ

本番地味に困ったのはa[x]、b[x]の算出なのだが、二分探索を思いつけて良かった。