これ意外に本番あっさり通してる。
http://codeforces.com/contest/920/problem/F
問題
D(x)をxの約数の個数とする。
数列Aに対し以下のクエリに順次答えよ。
- i∈[L...R]の範囲でA[i]をD[A[i]]に置き換える
- A[L..R]の総和を答える。
解法
D(x)は何回も適用すると近いうちに1に収束する。
よって「まだD(x)の適用により変化しうる要素の集合」を覚えておけば、クエリを繰り返すうちにだんだんこの要素がなくなり、前者のクエリはほとんどやることがなくなる。
あとは後者はBITで総和を取るだけ。
int table[1010101]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<ll,20> bt; int N,M; int A[303030]; char buf[10]; void solve() { int i,j,k,l,r,x,y; string s; for(i=1;i<=1000000;i++) { for(j=i;j<=1000000;j+=i) table[j]++; } scanf("%d%d",&N,&M); set<int> S; FOR(i,N) { S.insert(i+1); scanf("%d",&A[i+1]); bt.add(i+1,A[i+1]); } S.insert(N+1); while(M--) { int L,R; scanf("%d%d%d",&x,&L,&R); if(x==1) { x=L; while(x<=R) { auto it=S.lower_bound(x); x=*it; if(x>R) break; if(A[x]==table[A[x]]) { S.erase(it); } else { bt.add(x,-(A[x]-table[A[x]])); A[x]=table[A[x]]; } x++; } } else { cout<<(bt(R)-bt(L-1))<<endl; } } }
まとめ
Dのややこしさに比べるとだいぶ楽。