E問題をC++で解いてみました。ABC341は、2024年2月17日21:00に実施されました。紹介はこちらに、プログラミングの方針はこちらに記事があります。1223)問題はリンク先をご覧ください。String一工夫して、セグメント木を使います。持つ配列を計算します。入力例1をもとに計算してみます。0差分の配列は、以下となります。0最初に、クエリ2(1、3)を調べます。0差分配列の該当する箇所は、以下となります。0次のクエリ2(1、5)を調べます。0差分配列の該当する箇所は、以下となります。0次にクエリ1(1、4)で文字列を書き換えます。0差分配列を更新します。変化した文字を赤字にします。1再びクエリ2(1、5)を調べます。0差分配列の該当する箇所は、以下となります。1次にクエリ1(3、3)で文字列を書き換えます。0差分配列を更新します。変化した文字を赤字にします。1次のクエリ2(2、4)を調べます。0差分配列の該当する箇所は、以下となります。1差分配列の値を見れば、以下が分かります。クエリ1は、文字列を置き換えても、差分の配列は、端の2か所しか変化しない。0と1が反転しても、差分配列の途中の値は変わらない。プログラム例(ABC341E)セグメント木を使えば、端の値を更新しながら、指定された範囲の合計を求めることができます。この記事で紹介しています。差分配列をセグメント木に載せます。注意この問題では、クエリ1とクエリ2の添え字は、1からカウントしています。格納すれば、1からカウントする場合と整合が取れます。上に示した例と照らし合わせて確認してください。番目の要素に格納します(80ー81行目)。番目の要素を更新します。注意としては、LとRは問題に与えられた1からカウントした値を使います(89ー90行目)。なっているか)調べます(92行目)。以下が、C++プログラムとなります。Library(ACL)と呼ばれるライブラリが提供されています。使ったプログラムです。AC(Accepted=正しいプログラム)と判定されました。セグメント木を標準ライブラリとしては用意していません。プログラムは、なるべく言語標準のライブラリで実装したいと考えています。移植したプログラムの紹介を省略します。最後に更新するクエリと結果を返すクエリを処理する問題でした。セグメント木を使うことは予想ができましたが、下準備を思いつきませんでした。先週にセグメント木について記事を書いたため(記事1、記事2、記事3)、応用例を学んで使いこなせるようになりたいです。問題を紹介していきます。コメントをキャンセルメールアドレスが公開されることはありません。付いている欄は必須項目です上に表示された文字を入力してください。Contest)記事一覧ソフトウェア技術者アナダパンチ組込み製品の開発に従事しているソフトウェア技術者です。仕事でソフトウェア開発に従事しながら、趣味でもプログラミングを楽しんでいます。