パッと見であんまりよくわからなかったけど、解けてみると面白かったので。
こんなんセグ木に載るんかーといった感じでした。

解法

早い話が、全体の累積和と、各商品種（ $A _ i$ で分類される種類）の累積和をそれぞれ用意することができれば、各クエリに $O(1)$ で回答することができる。（ $[L, R)$ の範囲内の全体の累積和から、種類 $T$ の同じ範囲内の累積和の半分を引けばよい）
これを愚直に実装すると、たぶん小課題の1, 2, 3あたりまでは点数がもらえるはず。

満点解法もこれをベースにすることで作れる。
全体の累積和は、追加制約があろうがなかろうが簡単に作れる。しかし、各商品種の累積和を作るというのがメモリ制限でも実行時間制限でも厳しい。（それぞれ $O(N * min(M, N))$ 程度の時間/空間が必要）

そこで、辞書をセグメント木に乗せることを考える（HashMapとかunordered_mapとかdictとか呼ばれるもの）。
辞書には、そのノードがカバーする範囲の商品種をキー、商品種ごとの定価の合計を値として設定する。クエリの際は、 $T$ をキーに定価の合計値を辞書引きながらトップダウンに足し込んでいけばよい。

クエリの際の計算量はそれほど問題ではなくて、各ノードの辞書の検索は $O(1)$ と期待できるので、全体でも $O(log N)$ で捌くことができる。
ちょっと引っ掛かりそうなのはセグメント木の構築の部分の時間計算量と空間計算量だと思う。

構築の方法としては、左の子の辞書を自身にクローンしたうえで、右の子の辞書の内容を1つずつ愚直に反復して、自身に追加していくという方法がとれる。（重複要素があれば、足し込む）
時間がかかるのは子のクローンとイテレートで、これは子ノードの要素数が $n$ ならいずれも $O(n)$ 程度はかかる。
全ノード要素数が最大となるのは、 $N$ 個の商品の種類がバラバラのときである。具体的に要素数を見積もると、ある段の1つのノードの要素数が $n$ なら親ノードの要素数は $2n$ となるが、段全体のノードの数は半分に減るので、全体の要素数は変化しない。
また、1段分の全体としてのマージの計算量は、段全体の要素数からわかる（なぜなら、クローンとイテレートの計算量は要素数からわかるから）ので、結局 $O(N)$ である。
したがって、上記のような構築方法をとった場合、全体として $O(NlogN)$ 程度の時間計算量となる。