非想定解あるある、制約のせいで逆に迷った。 問題概要 atcoder.jp 考えたこと 今回は 1-indexed で考えた方が圧倒的にわかりやすいのでそのように統一する。 箱の色容量 色 $ i $ のボールを $ j $ 番目の箱に $ j $ 個入れる操作を「 $ 1 $ 色入れる」と定…

困ったときの平方分割。 問題概要 atcoder.jp 考えたこと 要素の総和が $ k $ の"素晴らしい整数列"の個数を $ f (k) $ とする。 また、このうち最後の要素が $ x $ であるものの個数を $ f _ x (k) $ とすると、 $$ f _ x (k + x) = f(k) - f _ x (k) $$ が…

問題概要 （筆者は問題を要約することに疲れたようです） atcoder.jp 考えたこと $ X_i $ の範囲を絞る $ L_i \leqq X _ {A_i} + X _ {B_i} \leqq R_i $ に着目する。 $ X_i $ のとり得る範囲を $ L ^ X _ i \leqq X_i \leqq R ^ X _ i $ とする。 仮に $ X …

結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。 問題概要 atcoder.jp 考えたこと クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。 √Q 回のクエリを 1 …

着想は公式解説とほぼ同じなのでかなり簡潔に記します。 問題概要 atcoder.jp 考えたこと 掃き出し法っぽい操作ができればよい。 A_i を区間 [i, i] であると考えて A(i, i) とする。 (k-1)-bit 目まで全て 0 であるような A(l, r) について、r の小さい順に…