座標計算はゼロ除算をやらかしやすい。
区間更新・1点取得ができるデータ構造を用いる。
Segment Tree や Fenwick Tree 等、1点更新・区間取得ができるデータ構造を用いると、 累積和からそれと同等のことが行える。 今回はFenwick Treeで足りる。
全ての需要を反映($[S_i,T_i)$ に $P_i$ を加算)した上で、 各時刻 $t$ につき $W$ をオーバーしていないか確認していくとよい。
時刻の上限 $T_{max}=2 \times 10^5$ として $O((N+T_{max})\log{T_{max}})$ で行える。
そもそも今回は途中経過が必要ないので、imos法による累積和でよかったね。
「時刻 $S_i$ に $P_i$ 需要が増える」「$T_i$ に $P_i$ 減る」という計 $2N$ 個のイベントを時刻順にソートして、先頭から需要量をシミュレートしていってもよい。
注意点として、同時刻の減るイベントと増えるイベントでは、減るイベントを先に処理するようにする。($T$ で終わる需要と $T$ で始まる需要は重複しないので)
この方法では時刻の長さ分の配列を用意する必要が無いので、時刻の取り得る範囲が $10^{18}$ など大きくても大丈夫。
右方向に2マス移動するのにも、「1手で2マス移動する」「1マス、1マスと2手かける」の2通りがある点に注意。
DPをするのだが、工夫しないとTLEになる。
たとえば、以下のようなDPを作って
更新時、以下のようにあるマスから遷移できる全てのマスに個別に遷移していると、$O(HW(H+W))$ となり、間に合わない。
同じ方向への移動を、上手くまとめてやる。
とすると、3マスからのみの遷移で済む。もらうDPでの遷移例を書くと、
つまり、例えば右移動で $(i,j)$ に至るのは $(i,j-1)$ からの遷移であり、その中でも「前と同じ方向(右)なら2倍」「異なる方向なら1倍」で足し合わせればよい。
───────┼──────────────┼─ (i, j-1) │(i, j) │ 0.→: 5通り │ 0.→: 5x2 + 2 + 8 = 20通り│ 1.↓: 2通り │ 1.↓: ... │ 2.↘: 8通り │ 2.↘: ... │
これは、以下を意味する。
これで、$O(HW)$ となり、間に合う。
もしくは、累積和を管理してもよいみたい。まぁ実質的に同じこととなる。
'1 a b
''2 x y
'Union-Findの拡張。
集合のリーダーに「自身の集合に各クラスが何人いるか」という情報をdict(連想配列)などで持たせておく。
最初は、1人1集合なので各 $i$ につき $\{C_i:1\}$ という情報を持っている。
Union-Find上でマージする際、このdictもマージする。リーダーの持つdict同士で一方にもう一方を合算する。
① {1:3, 2:5, 3:1} ┬→ {1:4, 2:5, 3:6, 4:2, 5:1} ② {1:1, 3:5, 4:2, 5:1} ┘
その際、dictの要素数が大きい方をベースとして、小さい方を統合する。
上例では、②をベースとし、①の方に対してイテレートを回して合算していく。
そうすることで、マージにかかる計算量は全体で $O(N\log{N})$ に抑えられる。
逆にこうしないと、意地悪なクエリでは最悪 $O(N^2)$ の計算量がかかる。
上記では、どちらをマージのベースとするかについてdictの要素数を基準としたが、 一般的なUnion-Findでも、集合のマージ時に「集合サイズを基準として大きい方に小さい方をマージする」というルールを使うことは多い。 この基準をそのままdictのマージに流用しても、下記のように多少非効率が生じうるが、およそ同様の効率化が図られる。 (敢えてそうする意味も薄いが、どちらをベースとするかが統一されるので混乱はしにくいかも)
① {1:1, 2:1, 3:1, ..., 9999:1} ② {1:10000} これは、dictの要素数で考えると①の方をベースとすべきだが、 集合サイズを基準とすると②がベースとなり、多少非効率になる しかし、①のようなデータを作るまでのマージや、 次にこのような非効率なマージが生じる場合を考えると、 非効率なマージが生じてしまう回数は限られると考えてよい ② {1:10001, 2:1, 3:1, ..., 9999:1} ③ {1:20000} ↑次に非効率なマージを生じさせるには、集合サイズが2倍以上になる必要がある