Hungry Cow

题目描述

注意：本题时间限制为 6s，是默认的三倍。内存限制为 512MB，是默认的两倍。 Bessie 是一头饥饿的奶牛。每天晚餐时，如果谷仓里有干草捆，她就会吃掉一个干草捆。Farmer John 不希望 Bessie 挨饿，所以在某些日子他会送来一批干草捆，这些干草捆会在早晨（晚餐之前）到达。具体而言，在第 $d_i$ 天，Farmer John 会送来 $b_i$ 个干草捆（$1\leq d_i \leq 10^{14}$，$0\leq b_i \leq 10^9$）。 现在处理 $U$ 次（$1\le U\le 10^5$）更新：给定一对 $(d, b)$，将第 $d$ 天到达的干草捆数量更新为 $b$。每次更新后，输出 Bessie 吃到干草捆的所有天数之和，对 $10^9+7$ 取模。

输入格式

$U$，接着 $U$ 行，每行包含一次更新。

输出格式

每次更新后输出一次答案：对 $10^9+7$ 取模的天数之和。

3
4 3
1 5
1 2

15
36
18

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

4005
4656
7607
3482
3507
3753
4058
1107
24531

提示

每次更新后的答案： 4+5+6=15 1+2+3+4+5+6+7+8=36 1+2+4+5+6=18 SCORING: Input 3: $U\le 5000$ Inputs 4-10: 更新只会增加第 $d$ 天到达的干草捆数量。 Inputs 11-22: 无额外限制。 题目贡献：Brandon Wang 和 Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum