AtCoder AGC #003 : E - Sequential operations on Sequence

コードは短いんだよな。
http://agc003.contest.atcoder.jp/tasks/agc003_e

問題

N要素の数列がある。初期状態で第i項はiである。
ここに対し、Q個のクエリを行う。
j番目のクエリは数値q[j]で表現され、その時点の数列を無限回繰り返したものに対し、先頭q[j]個を取る。

最終的に得られる数列に、1～Nが何回ずつ登場するか求めよ。

解法

Editorialより、他の人の解法の方がわかりやすかった。

i＜jに対しq[i]＞q[j]であれば、q[i]を実行する意味はない。
よってそのようなq[i]は無視してよい。
すると、考慮すべきq[j]は単調増加になるはずである。

N個の要素を繰り返すと考えると大変なので、逆に考えよう。
初期状態で、長さq[x] (q[x]は上記考慮すべき一連のq[j]のうち最上位のもの)のテープがあるとする。
これを何度か折りたたんだとき、1～Nの位置にどれだけテープが重なっているか考えよう。
上記q[j]を逆順にたどり、折りたたんでいく。
a＜b、q[a]＜q[b]の時、逆順にたどると長さq[b]のテープをq[a]に折りたたむので、全体はq[b]/q[a]回重なり、かつ先頭からq[b]%q[a]までの長さは1回多く重なる。

これを累積和の要領で、どこから重なる回数が増えるかをmapで管理する。
最終的に1～Nの位置にどれだけテープが重なったかを数えればよい。

int N,Q;
ll V[101010];
map<ll,ll> M;
ll RR[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	V[0]=N;
	FOR(i,Q) cin>>V[i+1];
	
	ll prev=V[Q];
	M[-prev]=1;
	for(i=Q-1;i>=0;i--) if(prev>V[i]) {
		prev = V[i];
		for(auto it=M.begin(); it!=M.end() && -it->first > prev; it=M.erase(it)) {
			M[-prev] += (-it->first)/prev * it->second;
			M[-((-it->first)%prev)] += it->second;
		}
	}
	FORR(r,M) RR[-r.first] += r.second;
	
	for(i=N+1;i>=1;i--) RR[i]+=RR[i+1];
	for(i=1;i<=N;i++) _P("%lld\n",RR[i]);
	
}

まとめ

最初コード見てなんでこれでうまく行くかわからなかったけど、落ち着いて考えたらわかった。