kmjp's blog

競技プログラミング参加記です

Codeforces ECR #037 : F. SUM and REPLACE

これ意外に本番あっさり通してる。
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のややこしさに比べるとだいぶ楽。