半環
考え方と注意
- 漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー)
- 漸化式をとにかく上手く作る
- 複数のパラメタを用いて順番に更新するような問題でパラメタが更新されるようなクエリがあっても、部分的に修正、高速に計算ができる
- セグメントツリーで計算する時に順番に注意
- 既存のセグメントツリーライブラリを使うのは良いが、順番通りに計算してくれていることを確認
- 行列累乗が使える条件として利用する場合もある
- この問題
- この問題では行列にmax(w+a,b)を乗せるという問題
- これはf(w)=max(w+a,b)として遷移関数を定義して解いている
- すると、合成関数（積）はmax(w+a+c,max(d+a,b))であり、和はmax(w + max(a,c), max(b,,d))となる
以下問題集
1. (整数,+,*)
ARC 008 D. タコヤキオイシクナール
2. (整数,xor,and)
ABC 009 D. 漸化式
3. (整数,max,+)
4. (行列,+,*)
Good Bye 2016 E. New Year and Old Subsequence
yukicode No.426 往復漸化式
AC Dangerous Hopscotch
https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d 解説
以下、短い解説
ARC 008 D. タコヤキオイシクナール
http://arc008.contest.atcoder.jp/tasks/arc008_4
半環 + セグメントツリー (+ 座圧)
解説
http://kagamiz.hatenablog.com/entry/2012/09/23/171835
https://kimiyuki.net/blog/2015/11/10/arc-008-d/
ABC 009 D. 漸化式
http://abc009.contest.atcoder.jp/tasks/abc009_4
半環 + 行列累乗
解説
http://n-knuu.hatenablog.jp/entry/2016/11/19/042628
https://www.slideshare.net/chokudai/abc009/
「みんなのプロコン」 D. 工場
http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d
半環 + セグメントツリー
解説
http://pekempey.hatenablog.com/entry/2017/03/07/023127
http://kmjp.hatenablog.jp/entry/2017/03/07/0900
Good Bye 2016 E. New Year and Old Subsequence
http://codeforces.com/contest/750/problem/E
半環 + セグメントツリー (+TrieとかオートマトンDP)
解説
http://pekempey.hatenablog.com/entry/2016/12/31/162212#E-New-Year-and-Old-Subsequence
http://kmjp.hatenablog.jp/entry/2017/01/02/0900
yukicode No.426 往復漸化式
http://yukicoder.me/problems/no/426
半環 + セグメントツリー
