直方体同士は体積が正の共通部分を持たない」 だったら N 個分書き込んでも総和は 100 万以下じゃん！ 隣のマスを見たら隣接直方体がわかるやん！ 提出 #44116267 (AC / 553 Byte / 729 ms)。■延長１日を含めてこれもう実質７完でいいんじゃね？ やったぜ！(めでたい)■■■G 問題。現在見ている頂点を３つ組の真ん中の頂点だと考えて直線トリオを数える DP ができるらしい(最後に３つ組の全選び方から引く)。提出 #44139844 (AC / 303 Byte / 634 ms)。そうすると直線ペアの数を数える必要がなくなって、サイズと直線トリオの数だけを数えればよくなったけど、期待に反してわずかに遅くなった。400 ms、500 ms 台に入ると思ったのになぜ？ 実は答えを合わせるのにすこし苦労して、現在見ている頂点を３つ組の真ん中に決め打つということは、他の２頂点を選んでくるのは子方向の部分木だけに限らず親方向からも選んでこられる(16 行目)。その点がこれまでの２つの解答と異なっていた(これまでは現在見ている頂点が LCA になるような３つ組を考えていたので問題が子孫方向の部分木に閉じていた)。■E 問題。たぶんだけど、サンプルにわかりやすーい図解が付随していたら当日の AC がもっと多かったと思う。問題文を読んでも全然具体的イメージが構築できなくて苦労したもんね。まず直方体の対角線って何だ、とか。それは長方形の対角線とは(必ず)違うと考えていいのか、と。不等号(X1<X2, Y1<Y2, Z1<Z2)に意味を持たせすぎないでもっと文章で説明してくれていいのよ。辺が軸に平行だということも、え、それってどういう、という疑問からなかなか先に進めなかった。脳内直方体は歪んでいた(それは直方体ではなくない？ 菱餅？ そんなつっこみも出てきやしなかった)。■■■F 問題。自分の提出は BIT を使ったせいで余分な log がついて時間がかかっていた。よく考えて整理した結果、２本の累積和から M 個を取ったあとで綱引きをするようにした。要するに尺取り。提出 #44215202 (AC / 619 Byte / 389 ms)。最速級まではいかないけど BIT 版より倍は早くなった。じっくり整理したので規則的で理解しやすいと思う。S2 に前加工を施すと k1x の補正が必要なくなるし、無意味に缶切りを取得する前に試行を中断できるけど、それは TODO。