TopCoder SRM 842 : Div1 Hard ColorfulStrip

Hardにしては簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=17921

問題

数列Xに対するハッシュ値を、h(X) = sum(X[i]*10^i)%1000000007で定める。

今N個のマスをC種の色で塗ることを考える。
初期状態は全マス0番の色で塗られている。

以下のクエリQ回分に順次答え、求めたハッシュ値からなる数列のハッシュ値を求めよ。

• 区間[L,R]のマスを色QCで上塗りする。
• 数列Pを、P[c] := 色cで塗られたマスの数 とし、そのハッシュ値を求めよ。

解法

クエリ毎にハッシュ値の差分更新をすることを考える。
色が変わるマス数を求められれば、Pの更新分だけハッシュ値を差分更新できる。
mapを使い、色が切り替わるマスの位置を覚えておけば、均しでmapの操作回数およびハッシュ値の差分更新回数はO(Q)であり、計算量はO(QlogQ)で済む。

const ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class ColorfulStrip {
	public:
	int recolor(int N, int C, int Q, int maxL, int seed) {
		ll state = seed;
		int i;
		vector<ll> F;
		ll cur=0;
		map<int,int> M;
		M[-1]=M[N]=0;
		M[0]=0;
		cur=N;
		while(Q--) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			int qlen = 1 + (state%maxL);
			state = (state * 1103515245 + 12345)%(1LL<<31);
			int L = state%(N+1-qlen);
			int R = L + qlen;
			state = (state * 1103515245 + 12345)%(1LL<<31);
			int NC = state%C;
			if(M.count(L)==0) {
				auto it=M.lower_bound(L);
				it--;
				M[L]=it->second;
			}
			if(M.count(R)==0) {
				auto it=M.lower_bound(R);
				it--;
				M[R]=it->second;
			}
			int CL=L;
			while(CL<R) {
				auto it=M.lower_bound(CL);
				int NCL=next(it)->first;
				(cur-=modpow(10,it->second)*(NCL-CL))%=mo;
				M.erase(CL);
				CL=NCL;
			}
			
			
			M[L]=NC;
			cur+=modpow(10,NC)*(R-L)%mo;
			cur=(cur%mo+mo)%mo;
			F.push_back(cur);
		}
		
		reverse(ALL(F));
		ll ret=0;
		FORR(f,F) (ret=ret*10+f)%=mo;
		return ret;
		
	}
}

まとめ

なんかSegTree使ってる人ちらほらいたけど、ない方がすっきり書ける気も。