解题思路
编号为 i 的哨站开通时,每座已开通哨站的补给券 x 变为 max(0,x−i),新开通哨站收到的总量为 ∑min(i,x)。
按开通天数升序记为事件 t=1,…,n,对应原编号 I[t](也是本次索取额度),初始储备为 A[t]。令前缀和 P[t]=∑k=1tI[k]。
对某座在时刻 r 开通的哨站,记它开通瞬间可供后续索取的总额为 S[r]。之后每个更晚的事件 t>r 会依次索取 I[t]:它会从 t=r+1 开始连续付满,直到某次 u 首次使得 P[u]−P[r]≥S[r],在 u 只付尾款,之后为 0。若直到最后都榨不干(P[n]−P[r]<S[r]),最终剩余 S[r]−(P[n]−P[r])。
于是每次事件 t 的收入可拆成:仍有余力的哨站数乘以 I[t],再加上恰好在本次被榨干者的尾款之和。用差分数组维护“仍能付满”的人数,用数组累加尾款,并用二分在前缀和上定位首次越界位置。