Range Multiplication Sum

2 secs 1024 MB
bayashiko

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