題目
USACO 2021 December Contest, Silver Problem 3. Convoluted Intervals
給 \(n\) 個 intervals \((a_i,b_i)\)。問對於 \(k=0\sim 2m\) 的每個 \(k\) 問有多少 pair \((i,j)\) 滿足 \(a_i + a_j \leq k \leq b_i + b_j\)
\(n\le 2\times 10^5,m\le 5000,0\le a_i,b_i \le m\)
思路
因為 \(m\) 只有 \(5000\),我們將開一個大小為 \(m\) 的 vector,第 \(x\) 格存 \(a_i=x\) 的 \(i\) 的數量,直接 \(m^2\) 枚舉 vector 裡面的 index
參考自 : https://www.usaco.org/current/data/sol_prob3_silver_dec21.html
code(from usaco)
CS Academy - Candles
給一個長度為 \(n\) 的陣列 \(a_1, ... ,a_n\) ,依序有 \(m\) 天,第 \(i\) 天要選 \(c_i\) 個數字減一,問最多能做能持續幾天
\(n, m \le 10^5\)
思路
greedy 策略,拿最大的 \(c_i\) 個出來減一。
先找到目前第 \(c_i\) 大的數字 \(x\)
-
大於 \(x\) 的所有數字都直接減一
-
假設數字 \(x\) 要刪除的數量是 \(t\),找到最左邊的 \(t\) 個 \(x\) 拿出來減一
這可以用線段樹來解決
CF 1919 F1. Wine Factory (Easy Version)
有座水塔,其中第 \(i\) 座包含 \(a_i\) 公升的水,且擁有一個能消除 \(b_i\) 公升水的法師。同時,相鄰兩座水塔之間擁有一道閥門,第 \(i\) 座高塔與第 \(i+1\) 座水塔之間的閥門允許通過 \(c_i\) 升水。
對於第 \(i=1,2,\ldots ,n\) 座塔,將會進行以下操作:
- 法師將水塔 \(i\) 中最多 \(b_i\) 公升的水消除,並將消除的水轉化為等量的紅酒。
- 如果 \(i \neq n\),那麼至多 \(c_i\) 公升水可以由閥門流到第 \(i+1\) 座水塔。
有 \(q\) 次單點修改,每次給出四個數字 \(p,x,y,z\),即將 \(a_p = x, b_p = y, c_p = z\),並要求對於每次更新,輸出最多能獲得多少公升紅酒。
\(n\le 5\times 10^5, a_i \le 10^9, c_i = 10^{18}, z = 10^{18}\)
思路
因為 \(c_i, z\) 均為 \(10^{18}\),那麼如果水塔中的水沒有被全部消除,則剩下的水均能流到下一座高塔,即可以不考慮 \(c_i\) 這個限制因素。
先考慮每座水塔本身無法消除的水量:\(v_i=a_i-b_i\),當 \(v_i > 0\) 時,未被消除的水量必然需要由後面的法師來進行消除(如果可以的話),因此對於水塔 \(k\) 而言,無法消除的水量實際上為 \(f(k)=\sum \limits_{i=k}^n v_i\)。那麼對於所有水塔來說,無法消除的水量即為 \(\max \{ f(1), f(2), \ldots ,f(n) \}\),因為前面的無法消除後面的,所以一旦某個後綴 \(f(i)\) 很大時,那些水就會被留在這個水桶 \(i\)。
使用後綴和建造一棵線段樹,維護區間上的最大值,並使用變數 \(\text{sum}\) 記錄水塔的總水量。
每次更新水塔 \(p\) 時,由於線段樹維護的是後綴和,那麼對於所有 \((p+1)\sim n\) 上的點,都不會收到影響,只需要對區間 \([1, p]\) 進行更新,先減去原本的 \(v_p\),再加上目前更新後的新 \(v_p = x - y\)。
那麼最後的答案就是 \(\text{sum} - \max \{ f(1), f(2), \ldots ,f(n) \}\),其中 \(\max \{ f(1), f(2), \ldots ,f(n) \}\) 為線段樹上的訊息。
2024 TOI 模擬賽 I pC. ⼩⽉⽼師的訊息追蹤系統
維護一個 stack,給 q 筆操作,分別有以下兩種:
-
加入一個新的元素至堆頂
-
將一個元素移至堆頂
輸出每個元素在堆裡最大是第幾層
\(q \le 10^6\)
思路
先看 subtask 2(每個數字都只移至堆頂一次),也就是當一個數字 x 被移到堆頂後,後面的任何操作都會去貢獻 x 的答案。回到我們原本的問題,如果一個數字 y 本來就已經在 x 上面,那他不管操作多少次,對於 x 的貢獻都是 1。所以我們得到一個結論: 如果 x 在第 i, j 個 query 都被操作了,那他在第 j 個 query 的時候的位置就是