c216: kevin 愛種樹

c216: kevin 愛種樹

題 意:

維 護 一 段 序 列 $A$，當 $A_i$ 超 過 $10^5$，$A_i$ 會 減 少 $10^5$。(ex: 100001 -> 1)

給 定 兩 個 操 作，

第 一 個 操 作 是 將 所 有 $A_i$ 加 上 $k$，並 維 持 上 面 的 條 件。

第 二 個 是 求 $[L, R]$ 的 總 和。

solve:

初 見 此 題，原 以 為 是 線 段 樹 的 操 作。但 是 想 了 想 發 覺 沒 這 麼 簡 單(也 有 可 能 是 我 太 爛)。

可 以 發 現 加 上 的 $k$ 其 實 可 以 模 $10^5$，也 就 是 $K$ 同 樣 可 以 模 $10^5$。

稍 微 將 問 題 的 答 案 化 簡 一 下，可 以 發 現 $Ans = S(L, R) - 10^5 \times count(A_i | i \in [L, R] , A_i >10^5 - K)$。

# 定 義 $count$ 為 其 集 合 元 素 個 數。

# $K$ 為 累 積 的 $k$

# 其 中 $S(L, R)$ 為 加 上 $K$ 後 的 區 間 總 和。

前 面 $S(L, R)$ 可 以 用 前 綴 和 $+$ $K * (R - L + 1)$。

難 的 是 後 面 的 詢 問，$[L, R]$ 裡 面 大 於 $10^5 - K$ 的 元 素 個 數。

設 $C$ 為 小 於 等 於 $10^5- K$ 的 元 素 個 數，那 我 們 所 求 即 為 $R-L+1-C$。

小 於 等 於 的 個 數 就 簡 單 了。

先 將 原 序 列 $A$ 排 序 為 $B$， 並 記 下 每 個 元 素 原 本 的 位 置。

接 著 再 將 所 詢 問 的 $C$ 由 小 到 大 排 序。

對 於 每 個 $C$，二 分 搜 $B$ 後，用 BIT 維 護 每 個 小 於 等 於 $C$ 元 素 的 位 置。

接 著 詢 問 BIT[L, R] 即 可 推 得 所 求。

code: