SparseTable
AtCoder
AtCoder600点
ABC-F
青色diff
インタラクティブ
データ構造
SparseTable
構築
区間
有名な性質に基づく背景のある問題
端から順に決まって行くGreedy
Greedy
被覆
コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに!」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…
AOJ
AtCoder
JAG
AOJ-ICPC
AOJ-ICPC700点
JAG夏合宿
二分探索
lower_bound
文字列問題
セグメント木
SparseTable
SuffixArray
文字列検索問題
クエリ処理問題
制約:複数系列の長さの合計が10^5以下
連続部分列を扱う問題
区間
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
Disjoint Sparse Table の勉強をした!!! 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…