# 数列

## ソートをしても一般性を失わないならソートする
ソートされていると扱うのが簡単になる例は多い

## 条件を満たすi,jのペアの数
値を辞書で管理しておくと判定が簡単になる場合が多い

## 条件を満たすi,j,kの3値の数
どれかの値を固定すると見通しがよくなる。
最初に全ての値をdataRに入れておき、jをシフトすると共にdataLにjだった値を入れていけば、jを中心とした時の左右の値を管理できる。

管理の仕方としては存在確認をしたいなら辞書、ある範囲の数を数えたいなら、BITなどで持たせる。
- 例、 jの値を中心として、より小さい左の値、より大きい右の値の数をカウントしたいならBIT管理が適する

## 区間和の最大
初期値を0として頭から和にして、値が負になったら0にリセットし、次の数からスタートとする。
ある地点で負になった場合、その値を次からに持ち越す必要はなく、次の値から始めた方が良い。

# グラフ

## ダイクストラ法
- 単一始点、全終点を求める。
- 負のサイクルがあってはいけない。負の辺があること自身は許容される
- 各点について更新した１つ前の点を覚えておくことで始点からのパスを求めることが可能
  - 全点についてこのパスを復元すると、辺数は$n-1$の全域木となる（最小全域木とは限らない)

## ハミルトン

# 閉路を含むグラフ
- 強連結成分分解をするとDAGになるので、木にできる

# 木
## 葉から辿る・根から辿るにはトポロジカルソートを使っても良い
- 根からトポロジカルソートをすると、順に辿れば根から辿れる。逆に辿れば葉から辿れる。DFSして良いが、なにも考えずにライブラリで配列の形で計算を流せる。

# データ構造
## SparseTable　
- 更新不可、区間クエリO(1)
- 事前計算 O(logN) クエリO(1)