2013-10-08から1日間の記事一覧
問題 要素数N()の数列が与えれる。[a,b]区間の最大値と最小値の差分を求めなさい。 解法 セグメント木を使う。最大値を保持する配列と最小値を保持する配列の2つを持つ。 計算量 更新: クエリ: コード
問題 N()人の名前と値が与えられる。初めにK番目の人(1から始まる)からスタートし、選ばれた人は抜ける。抜ける際に、p番目の人はpの約数だけ飴がもらえる。次の人は、その人の値分だけ時計回りした番号の人になる。マイナスの場合は逆回転となる。飴の最大…
問題 N*N()の配列が与えられる。各要素は、1か0しか値をとることができない。ふたつのクエリに対する処理を実行せよ。 (x,y)の要素が1なのか0なのか求めよ (x1,y1,x2,y2)の範囲をフリップせよ 解法 二次元のBITを使い、範囲操作をするために4つの二次元BITを…