Range Multiplication Sum

愚直に処理すると計算量は となり、間に合いません。
なので、一点更新・区間和を処理できるセグメント木を つ用意し、それぞれ と を載せることにすると各クエリを で処理できます。
全体の計算量は です。