c260: 吃蛋糕

c260: 吃蛋糕

題 意 : 
給 定 一 段 數 列，問 有 多 少 區 間 滿 足 區 間 平 均 值 在 [a, b] 內?

例 如 : 數 列 = [1 5 15], a = 3, b = 7，[5], [1 5], [1 5 15] 這 三 段 符 合 要 求，所 以 答 案 為 三。

solve:
先 列 出 不 等 式，$a \leq {sum_{l,r}\over n'} \leq b$，$n'$ 為 區 段 長。
將 不 等 式 乘 上 $n'$，分 成 兩 個 不 等 式
--  $a \times n' \leq sum_{l,r} $  ==>  $0 \leq sum_{l,r} - an'$
--  $sum_{l,r} \leq b \times n'$   ==>  $sum_{l,r} - bn' \leq 0$

顯 然 如 果 將 原 數 列 轉 成 兩 個 分 別 減 去 a, b 的 數 列 可 以 簡 化 成
--  $0 \leq sum'_{l,r}$
--  $sum''_{l,r} \leq 0$
這 樣 就 變 成 了 區 間 值 大 於/小 於 等 於 0 的 問 題，而 這 個 問 題 可 以 輕 易 的 用 前 綴 和 求 逆 正/序 對 解 決。不 過 這 裡 的 正/逆 序 對 定 義 並 非 一 般 的 定 義，可 以 自 己 想 想。

接 著 就 是 把 兩 個 答 案 合 起 來，根 據 排 容 原 理 A + B - AUB = A∩B 可 以 知 道。

正/逆 序 對 那 裏 可 以 用 BIT + 離 散 化 做，不 過 碼 量 比 merge sort 多，所 以 我 就 用 merge sort 了。

code: