drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ YosupoLibraryChecker NoviSteps2D SWAG クエリ処理問題 操作:区間 一次関数の合成 関数の合成 操作:先頭や末尾の要素の削除 操作:先頭や末尾への挿入 データ構造 deque SWAG を履修した！ 問題へのリンク 問題概要 一次関数の列を考える。初期状態では空である。以下の 個のクエリを処理せよ。 クエリタイプ 1 ()：一次関数 を列の先頭に挿入する クエリタイプ 2 ()：一次関数 を列の末尾に挿入する クエリタイプ 3：列の先頭の要素を削除する クエリタイプ 4：列の末尾の要素を削除する クエリタイプ 5 ()：列を としたとき、 の値を 998244353 で割った余りを出力する 制約 解法 モノイド (セグ木の要件と同じ) の列に対して、以下のクエリに の計算量で答えられるデータ構造として SWAG がある (参考資料)。 列の末尾に要素 を挿入する 列… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F05%2F05%2F175309" title="Yosupo Library Checker - Duque Operate All Composite (2D) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2024-05-05 17:53:09 rich https://drken1215.hatenablog.com/entry/2024/05/05/175309 1.0 100%