競技プログラミング用知識集積所

ABC419D - Substr Swap

最終更新：2025年08月17日 00:54

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

i文字目は最終的にSとTで入れ替わっているのかそうでないのか、を各文字ごとに調べればよい。
しかし、各文字ごと各クエリごとループを回すと間に合わない。
そこで、「結局その場所は何回入れ替えるの？」を考えて、最後に奇数回のところだけ入れ替えることにする。

「結局その場所は何回入れ替えるの？」は、範囲にまとめて1加算したい、となれば階差数列※の出番。
1を足したい先頭に+1、1を足したい末尾の次に-1、で全操作分集計してから累積和を取れば、高速に求められる。

タグ：

階差数列累積和

競技プログラミング用知識集積所

記事メニュー

人気タグ「」関連ページ

人気記事ランキング

最近更新されたページ

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！