tubo28 https://blog.hatena.ne.jp/tubo28/ tubo28のブログ https://tubo028.hatenablog.jp/ データ構造 UVa 平方分割 問題 個の可変抵抗が直列に繋がれている。 番目の抵抗を に変更 区間 の合成抵抗を出力(直列だから足すだけ) という指示が来るので順番に処理せよ。 平方分割 抵抗もクエリも多いので普通に足すだけだとTLEする。 以前にあり本のFenwick Treeをコピペして解いたけど、平方分割のバケット法というテクニックを知ったので、その練習のためにやり直した。 このスライドが参考になった。 http://www.slideshare.net/iwiwi/ss-3578491 FenwickTreeは更新が ,出力も 、平方分割による 分木だと更新に ,出力に かかる。実際に掛かった時間はFenwickT… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftubo028.hatenablog.jp%2Fentry%2F2014%2F06%2F30%2F174028" title="平方分割のバケット法で区間の和を効率的に求める (UVa 12086 Potentiometers) - tubo28のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%7BN%7D Hatena Blog https://hatena.blog 2014-06-30 17:40:28 rich https://tubo028.hatenablog.jp/entry/2014/06/30/174028 1.0 100%