Codeforces #185 Div1 D. Interval Cubing

だいぶ前にEditorialをチラ見してたのを覚えていたので、そのあとはあっさり解けた。
http://codeforces.com/contest/311/problem/D

問題

N要素の数列A[i]がある。
この数列に対し、以下のQ個のクエリを処理せよ。

• L,Rに対し、A[L]～A[R]の和を返す。
• L,Rに対し、A[L]～A[R]をそれぞれ３乗した数値に置き換える。

なお、答えが大きくなる場合は95542721の剰余を答えよ。

解法

「ある整数を３乗する」という処理は48回繰り返して95542721でmodを取ると元に戻る。
よって、まず最初に各A[i]について48通りの値を列挙し、かつ累積和を求めておく。

あとは平方分割。
２つ目のクエリは、L～Rの区間でとりうる値が48通りの中で1進むことを意味する。
これらの総和は事前の累積和で簡単に求められる。
もし２つ目のクエリがいくつかたまったら、一旦A[i]を整理する。

１つ目のクエリがあったら、整理後に登場した２つ目のクエリの情報を用いて求める値を出す。
整理後２つ目のクエリがM個あったら、48通りのうち値が変わる場所は高々2*M個なのでO(M)で求めることができる。

なお、今回の問題はA[i]の累乗を48通り出す処理がそこそこ重いので、A[i]を整理する境目が√NだとTLEする。
以下のコードでは3000でも整理が重く、10000では１つ目のクエリが重く、TLEするので、4000～6000程度と絶妙な値を取らないといけないのがつらい。

BITでやった方が若干速そうね。

int N,Q;
int tc[100002];
ll A[50][100002],S[50][100002];
ll mo=95542721;
map<int,int> M;

void build() {
	M[0]=M[N+1]=0;
	int cur=0,i,j;
	map<int,int>::iterator mit=M.begin();
	mit++;
	
	FOR(i,N) {
		if(mit->first==i+1) cur+=mit->second, mit++;
		tc[i+1]+=cur;
		FOR(j,48) S[j][i+1]=(S[j][i]+A[(j+tc[i+1])%48][i+1])%mo;
	}
	M.clear();
	M[0]=M[N+1]=0;
}

ll dodo(int id){
	int cur=0;
	map<int,int>::iterator mit=M.begin();
	ll ret=0;
	
	while(mit->first<=id) {
		int pre=mit->first;
		cur+=mit->second;
		mit++;
		if(pre>=0) ret += S[cur%48][min(id,mit->first-1)]-S[cur%48][pre-1];
	}
	
	return ret;
}

void solve() {
	int i,j,k,l,r; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[0][i+1];
		A[0][i+1]%=mo;
		FOR(j,48) A[j+1][i+1]=A[j][i+1]*A[j][i+1]%mo*A[j][i+1]%mo;
	}
	build();
	
	cin>>Q;
	while(Q--) {
		cin>>i>>l>>r;
		if(i==1) {
			cout<< ((dodo(r)-dodo(l-1))%mo+mo)%mo << endl;
		}
		else {
			M[l]++;
			M[r+1]--;
			if(M.size()>5000) build();
		}
	}
}

まとめ

平方分割の閾値をかなりきっちり設定しないとTLEするので、あまりいい解法じゃないのかも。