競技プログラミング提出へのリンクセグメント木でやろうとして90分くらい使ったらもう眠いしわからんしで解説読んだらシンプルな累積和でよかった。歯を磨いてたら解説の図が頭の中でどうも引っかかって、正方形ではなくてその左上半分ではないかという気がする。制約外せば正方形ではあるが...(制約はずさなくても正方形で描くほうが適切であることに記事の後半で気づいた)眠くて理解しきれていないので解法を丁寧に書く。累積和を計算しておいている。走らせたものなのでこういうコードになっている。いうように続いていく。してみると解説冒頭の図が正方形になっているのはむしろ自然だ。ある要素までの総和が取り出せて、適切な区間で切って引き算すればある部分列の総和が取り出せる。そんな累積和の部分的な和のさらに総和が今回の答え。なんか高校数学みたいな問題だなあ。工夫して用いることで効率的な計算ができるらしい。競技プログラミング提出へのリンク全頂点が最大200個なのでワーシャルフロイド法を使うことができる。