Range Update Query

Falling Balls | CS Academy #67

dp[i][d]:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」とする。 iをyの昇順に決定することでこのDPを解ける。よって、事前にソートしておくことでi<=j ⇔ y[i]<=y[j]とする。台iの端dからボールが落ちたとする。このとき、x[i][d]…