[EGOI 2023] Inflation / 通货膨胀

Luogu

IDLGP9463

Time3000ms

Memory1024MB

DifficultyP3

2023O2优化EGOI（欧洲/女生）

众所周知，瑞典南部的人们经常吃沙拉三明治。沙拉三明治的价格波动很大，分析经济情况的最好方法是每天去同一家沙拉三明治店，把菜单上所有价格都加起来。一家沙拉三明治店的菜单上有 $N$ 个不同的菜品。第 $i$ 个菜品有价格 $p_i$。每天，下列事件之一发生： - `INFLATION x`：所有价格增加 $x$。 - `SET x y`：每个价格为 $x$ 的菜品的价格更改为 $y$。你的任务是处理 $Q$ 天，在每天结束后输出所有菜品的总价格。 ## Input 第一行一个整数 $N$，表示菜品数量。第二行 $N$ 个整数 $p_1,p_2,\cdots,p_N$。第三行一个整数 $Q$，表示天数。接下来 $Q$ 行，每行一个字符串 $s$ 和一至两个整数。如果 $s$ 是 `INFLATION`，接下来一个整数 $x$。表示当天所有价格增加 $x$。如果 $s$ 是 `SET`，接下来两个整数 $x,y$。表示每个价格为 $x$ 的菜品的价格更改为 $y$。 ## Output 输出 $Q$ 行，每天结束后所有菜品的总价格。 [samples] ## Background Day 1 Problem A. 题面译自 [EGOI2023 inflation](https://egoi23.se/assets/tasks/day1/inflation.pdf)。 [![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/) ## Note **样例 $1$ 解释** 下图为样例 $1$ 的前两天。注意到第一天结束后价格总和为 $16$，所以输出的第一个整数为 $16$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/jnt1pk1u.png) --- **数据范围** 对于全部数据，$1\le N\le 3\times 10^5$，$1\le p_i\le 10^6$，$1\le Q\le 10^5$，$1\le x,y\le 10^6$。 - 子任务一（$14$ 分）：$N=1$。 - 子任务二（$28$ 分）：$N,Q,p_i,x,y\le 100$，依赖于子任务一。 - 子任务三（$19$ 分）：只有 `INFLATION` 事件。 - 子任务四（$23$ 分）：只有 `SET` 事件。 - 子任务五（$16$ 分）：无特殊限制，依赖于子任务二、三、四。 --- **提示** 答案可能不在 $32$ 位整型范围内，如果你使用 C++ 语言，请注意溢出的可能。

Samples

Input #1

5
2 1 1 2 5
6
INFLATION 1
SET 3 2
SET 5 2
INFLATION 4
SET 6 1
SET 10 1

Output #1

Input #2

3
1 4 1
5
SET 1 1
SET 3 4
INFLATION 2
SET 3 1
SET 6 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[EGOI 2023] Inflation / 通货膨胀",
    "description": {
      "content": "众所周知，瑞典南部的人们经常吃沙拉三明治。沙拉三明治的价格波动很大，分析经济情况的最好方法是每天去同一家沙拉三明治店，把菜单上所有价格都加起来。 一家沙拉三明治店的菜单上有 $N$ 个不同的菜品。第 $i$ 个菜品有价格 $p_i$。 每天，下列事件之一发生： - `INFLATION x`：所有价格增加 $x$。 - `SET x y`：每个价格为 $x$ 的菜品的价格更改为 $y$。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9463"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "众所周知，瑞典南部的人们经常吃沙拉三明治。沙拉三明治的价格波动很大，分析经济情况的最好方法是每天去同一家沙拉三明治店，把菜单上所有价格都加起来。\n\n一家沙拉三明治店的菜单上有 $N$ 个不同的菜品。第 $i$ 个菜品有价格 $p_i$。\n\n每天，下列事件之一发生：\n\n- `INFLATION x`：所有价格增加 $x$。\n- `SET x y`：每个价格为 $x$ 的菜品的价格更改为 $y$。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments