タイプが全部指定されているときのきれいな解き方を考える．

各 \(i\) (\(1 \leq i \leq N\)) に対して，（\(N\) 個の仕事を \(N\) 日で終わらせるという前提のもとで）\(i\) 日目までにできる仕事 L の数の最大値を \(d_i\) とする．

主張：すべての \(i\) に対して同時に \(d_i\) を達成するような解が存在し，当然これが最適解である．

証明は後述．

具体的に \(d_i\) を求める方法を考える．

\(N\) 個の仕事を \(N\) 日で終わらせるという前提を忘れて，タイプ L の仕事だけを考える． これらの仕事をできるだけ早くやるという貪欲を考える． この時タイプ L の仕事を行った日を \(x_1 < x_2 < \cdots < x_k\) とおく．

同様に，\(N\) 個の仕事を \(N\) 日で終わらせるという前提を忘れて，タイプ R の仕事をだけを考える． これらの仕事をできるだけ遅くやるという貪欲を考える． この時タイプ R の仕事を行わなかった日を \(y_1 < y_2 < \cdots < y_k\) とおく．

\(d_i\) の上界として，\(\min(\)「\(x_j \leq i\) を満たす \(j\) の個数」\(,\)「\(y_j \leq i\) を満たす \(j\) の個数」\()\) という値が考えられる． この値が \(d_i\) に一致する．

具体的な構成としては，タイプ L の仕事のうち，番号の早い方から \(i\) 番目のものを \(\max(x_i,y_i)\) 日目に行えばよい（※1）．

タイプの変更クエリを処理する． \(1\) つの仕事を L に変更することは，\(x,y\) にそれぞれ \(1\) 要素ずつ足すことに対応する．

各 \(i\) (\(1 \leq i \leq N\)) に対し，\(e_i=\)「\(x_j \leq i\) を満たす \(j\) の個数」\(-\)「\(y_j \leq i\) を満たす \(j\) の個数」と定義する． \(\sum |e_i|\) が求まれば，そこから \(\sum d_i\) が計算でき，そこからさらに問題の答えが求まる．

\(x,y\) への要素の追加は，\(e_i\) に対する区間 \(\pm 1\) になる． 一般の区間 \(\pm 1\) と \(\sum |e_i|\) の取得を処理する平方分割解法があるが，計算量が \(O(N \sqrt{N})\) となり，今回の問題の制約だとTLが厳しい．

そこで次のような解法を考える． 区間 \([l,r)\) に \(v\) (\(=\pm 1\)) を足すとき，\([l,r)\) 内の \(e_i\) の値を符号で分類する． そして，符号が同じ区間はまとめて処理することにする． segtree上の二分探索を用いることで，\(O(\)区間の数 \(\times \log (N))\) 時間での更新が可能になる．

一般の区間addでは区間の数が全体で\(O(N^2)\)になってしまうが，この問題では全体で\(O(N)\)であることが証明できる（※2）． よってこの方法で更新を行えば \(O(N \log N)\) 時間解法が得られる．

解答例(C++)

（※1）部分の証明について

タイプが固定されたときの解き方として別の方法を考えると証明しやすい． 具体的には，次のような貪欲を考える．

• \(1,2,\ldots\) 日目に行う仕事を \(1\) つずつ決めていく． L の仕事を行える（その日にできるL の仕事が残っていて，かつそれを行ったとして，残りの仕事を全部終わらせることができる）なら L をやり，不可能なら R をやる．

この貪欲の正当性としては， L を後回しにした場合，必ずその L を左に持っていくような組み換えが存在することから示せる． そして，この貪欲の結果が \(\max(x_i,y_i)\) で求めた解と一致することも確認できる． 「その日にできるL の仕事が残っていて」が \(x_i\) に対応し，「かつそれを行ったとして，残りの仕事を全部終わらせることができる」が \(y_i\) に対応する．

（※2）部分の証明について

問題を最小費用流で定式化すると見やすくなる． 仕事を 1 つ R \(\to\) L と変更したあと，負閉路を見つけて流すという操作を考える． この負閉路の構造が単純で，各日を L,R どちらで使ったかという列を考えると，この列の部分列を rotate する構造になる．なお実際には R \(\to\) R \(\to\) R のようなフローが流れることもあるが，LR 列では変化がないため，これは省略する． （↓rotate の例）

RRLLRRLLRR
         ↑ここを `L` に変更

RRLLRRLLRL
*  * *   * ここを rotate

LRLRRLLLRR

解説した解法における区間の個数は，ここでの rotate に含まれる要素の個数に対応する． rotate の回数は，以下のポテンシャルを考えると見積もれる．

• 各 R タスクについて，それをやる日 \(x\) と締切 \(r\) に対して，区間 \([x,r]\) を考える． これらの区間すべての union をとり，区間の集合を得る．これらの区間の長さの総和をポテンシャルとする．

R \(\to\) L の変化が仕事 \([L_i,R_i]\) に対して起きたとする． \(L_i\) 及び \(R_i\) をまたぐ区間については，rotate 後に長さが変わらないか減るだけである． \([L_i,R_i]\) 内に完全に含まれる区間については，rotate で操作されると長さが \(1\) 減る．

これで rotate の操作回数が \(O(N)\) であることが示せた．