2020年3月20日その他区間和,区間,累積和,配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...

2020年3月15日AtCoder競プロ,セグメント木,区間,更新,データ構造,set,imos法,遅延評価セグメント木,イベントソート,座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻&n ...

2020年3月10日動的計画法DP,テーマ記事,競プロ,区間,区間DP,区間の除去・圧縮・合体

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。

区間DPとは

区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。

基本的には、以下のような DP ...

2020年3月8日AtCoder剰余,数え上げ,500点,競プロ,区間,素数,Pで割り切れる

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか?

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

2020年3月6日その他区間和,テーマ記事,競プロ,区間,累積和,imos法,二次元区間和

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理:\(O(N)\)
クエリ:\(O(1)\)

で処理がで ...

2020年3月5日データ構造BIT,区間和,競プロ,二分探索,セグメント木,区間,データ構造,RAQ,RSQ,転倒数

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...

2020年3月2日AtCoder500点,セグメント木,区間,set,クエリ

問題概要

長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。

S の \(i_q\) 番目を \(c_q\) に変更する
S の \(i_q\) 番目から \(r_q\) 番目ま ...

2020年2月27日データ構造二分探索,セグメント木,二分木,完全二分木,区間,モノイド,更新,RMQ,RUQ,データ構造

セグメント木とは

セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...