コンテストへのリンク
No.1000 Point Add and Array Add
まず、クエリBだけの場合を考える。
これは、BITを使って処理できる。
たとえば、
・B 2 5
というクエリに対しては、BIT上の2に+1、6に-1をしておけば良い。
最終的にそれぞれの要素を何回ずつ使ったかが分かるので、できあがる数列が分かる。
次にクエリAを処理する。
「A x y」というクエリだったら、このクエリが来る前にxを何回処理していたかが分かれば良い。最終的に何回使ったかはBITにより分かるので、そこから引けば、増加分yが何回寄与するかが分かる。
No.1001 注文の多い順列
kmjpさんのブログの方針で解説AC。（包除原理を使う方針は理解できていません）
kmjpさんの記事の、「前者だが逆に考えよう」以下の説明が難しいけれど、これは本当に逆に考えれば良さそう。
つまり、「もし逆に、大きい数字から埋めてきたとしたら」と考えたとき、この数字を埋める方法は何通りあるか？ と考えると、掛けるべき係数が得られる。
これでDPが回るのはちょっと不思議で、正当性を説明・証明しろと言われると自信がないんだけど……。でも、確かにこれで立式できているし……。
0 件のコメント:
コメントを投稿