ランレングス圧縮 メモ

操作区間の長さに対して、区間内の要素の種類数が十分少なくなるような操作

→ランレングス圧縮により、区間に対する操作の計算量をO(区間長)からO(区間内の要素の種類数)に落とせる

→各項の値に上限があるときに、単調な列を作ることがO(n)でできたりする

(→凸包の片側を作る,etc)

 

数列の片端にしか操作をしない場合はstack

圧縮した区間の分割がある場合はmap

 

参考

蟻本 298p

 

stack

https://codeforces.com/contest/1313/problem/C2

https://atcoder.jp/contests/past202004-open/tasks/past202004_g

 

 map

https://atcoder.jp/contests/agc029/tasks/agc029_c