c782: PC. 孤單值量測

c782: PC. 孤單值量測

題 意:

在 一 條 馬 路 上 有 $n$ 個 人，每 個 人 都 站 在 一 個 位 置 $a_i$，都 有 一 個 孤 單 評 測 值 $w_i$。現 在 里 長 想 計 算 這 些 人 的 孤 單 值 總 和，如 果 第 $i$ 個 人 和 第 $j$ 個 人 的 位 置 相 差 大 於 $k$ 公 尺，那 麼 他 們 會 對 總 孤 單 值 $S$ 貢 獻 $w_i*w_j$。現 在，請 你 幫 我 求 出 $S$。

solve:

先 做 $w_i$ 的 前 綴 和，從 後 面 用 $l$, $r$ 兩 指 標 不 斷 求 出 距 離  $a_r$ 大 於 $k$ 的 人，可 以 看 出 $w_r * Sw_l$ 就 是 $a_r$ 的 貢 獻。

code: