本番だいぶ混乱したけど何とか正答。
http://codeforces.com/contest/474/problem/F
問題
N匹の蟻の強さはS[i]である。この時、以下のクエリT個に回答せよ。
- クエリはL[i], R[i]の2値で構成される。L[i]≦x≦R[i]である各xに対して、同じくL[i]≦y≦R[i]であるyのうち1つでも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]の算出なのだが、二分探索を思いつけて良かった。