Lucky Queries (Codeforces 145 E)

http://codeforces.com/problemset/problem/145/E

問題

4,7で構成される長さnの列がある。m個のクエリが来るのでさばけ。クエリは次の2種類。

• 区間[l, r]の4と7を反転させるクエリ。
• 区間[1, n]の非単調減少列の長さを答えるクエリ。

1<=n<=10^6
1<=m<=3*10^5

解法

セグメントツリーを使う。各ノードに4の数、7の数、444...4477...77の列の長さ、77...7744...44の列の長さを保持しておけば、2つ目のクエリにはO(1)で答えることができ、区間[l, r]を反転させるクエリに1回だけ対応することができる。このままでは、重なっている区間に対して2回反転をさせようとすると不整合が起きてしまうので、さらに各ノードに対して現在その区間が反転してるかどうかを保持させる。こうしておけば反転したいときに、セグメントツリーの中のその区間に対応するノードの途中で訪れた区間が反転している場合は子の区間を両方反転させることによって不整合を防ぐことができる。このように区間の反転をなるべく遅延させることによって1つ目のクエリをO(logn)でさばけるようになる。