# ABC196 (2021/12/10)

## A
$b-c$

## B
`basic_string::substr`, `std::find`, `basic_string::find`

## C
$O(\log N)$
間に合う場合は書きやすい方を採用
(二分探索)

## D
DFS

類題：https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/3248 (模擬国内2021C)

Dの公式解説の$HW \leq 200$は$H$と$W$の小さいほうでbitDP
類題：蟻本のbitDPの章(p177)

## E
区間 update + 二分探索
`std::clamp`

ちょっと違うけど、関連として
- slope trick
- segment tree beats

## F
${\rm popcount}(S[i:i+|T|]\ {\rm xor}\ T)$ の最小値
もうちょっと時間欲しい…

## 雑談
Monotone Minima について
yukicoder 952が解ける？

https://yukicoder.me/submissions/421593
データ構造
Link-Cut木 辺を切ったりつなげたりしてそれぞれの部分木やパスの情報などを取得できる
## Luzhiled's Library
### 分割統治法
蟻本 点の距離の最小値
~~数列 差が K 以下の 2 要素について距離を足し合わせたもの~~
これは違うっぽいけど、こんな感じで数列に対して行うと 2 乗が log になり間に合うことがある、yukicoder にいくつかあった気がする
### ナップサック
ほぼ蟻本で十分
形式的冪級数
戻すDP
### 最大長方形
最大正方形（HW のやつではない・自作、O(N)）も可

### Monotone Minima

陽にもてない $N\times M$ の Monotone 行列の各行の最小値を求める
アルゴリズム:
> 中央の行について全部計算
> 最小値をとる位置の左上と右下だけを再帰的に計算

Monotone $\subset$ Totally Monotone $\subset$ Monge
Monge: 距離関数の $n$ 乗 $(L_p)^n$ は大体満たす
Monge ... $f(a,c) + f(b,d) \le f(a,d) + f(b,c)\ (a \le b \le c \le d)$
Monotone ... $\forall i, \arg\min_j({A_i}_j) \le \arg\min_j({A_{i+1}}_j)$
- Divide and Conquer Optimization
- 2次元 DP の各遷移に適用
- オンラインオフライン変換
- 1次元 $O(N\log^2 N)$