[BCSP-X 2024 12 月小学高年级组] 操作序列

Luogu

IDLGB4161

Time1000ms

Memory512MB

DifficultyP5

线段树2024北京差分BCSP-X

有 $n$ 个变量 $x[1 \sim n]$，初始值都为 0。依次给出 $m$ 个操作的信息，操作分为 2 种： - $(1, id, v)$: 代表将 $x[id]$ 的值加上 $v$； - $2$: 代表将所有变量的值乘 $2$；所有运算在 $(\bmod \ 10^4)$ 下执行，提示：模意义下的加减乘运算 - 加：`c = (a + b) % mod`； - 减：`c = (a - b + mod) % mod`； - 乘：`c = a * b % mod`；现在给出一个操作序列，请问依次执行序列中的所有操作之后，每个变量的值是多少。具体的，操作序列以 $q$ 个区间 $[l[i], r[i]]$ 的形式给出，依次执行每个区间、每个区间按编号从小->大执行区间内的操作，即完整的操作序列为： - $l[1] \sim r[1], l[2] \sim r[2], l[3] \sim r[3], \ldots, l[q] \sim r[q]$ ## Input 第一行 $3$ 个整数 $n, m, q$，代表变量数量，操作数量，操作序列中区间数量。接下来 $m$ 行，每行 $3$ 个整数 $op, id, v$ 或者 $1$ 个整数 $op$，给出所有操作的信息。接下来 $q$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表一个操作区间。 ## Output 输出一行 $n$ 个整数，代表所有操作执行完之后每个变量的值。 [samples] ## Note ### 样例 3-8 见附件。 ### 数据范围对于所有数据，$1 \leq n, m, q \leq 2 \times 10^5, op = \{1, 2\}, 1 \leq id \leq n, 1 \leq v \leq 10^9$，假设 $m$ 种操作中第 1、2 种操作的总数为 $m_1, m_2$，满足 $m_1 + m_2 = m$。本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。 | 子任务编号 | 分值 | 数据范围 | 特殊性质 | 子任务依赖 | |:------------:|:------:|:----------:|:----------:|:------------:| | 1 | 15 | $n, m, q \leq 500$ | | | | 2 | 19 | $n, m, q \leq 5000$ | | 1 | | 3 | 11 | $n, m, q \leq 2 \times 10^5$ | $m_2 = 0$ | | | 4 | 17 | $n, m, q \leq 2 \times 10^5$ | $m_1 = 1, m_2 = m - 1$ | | | 5 | 17 | $n, m, q \leq 2 \times 10^5$ | $m_1 = m - 1, m_2 = 1$ | | | 6 | 21 | $n, m, q \leq 2 \times 10^5$ | | 1,2,3,4,5 |

Samples

Input #1

Output #1

228 0 48 0 0

Input #2

Output #2

2536 0 0 8952 3560 0 6304 4674 0 0

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 12 月小学高年级组] 操作序列",
    "description": {
      "content": "有 $n$ 个变量 $x[1 \\sim n]$，初始值都为 0。 依次给出 $m$ 个操作的信息，操作分为 2 种： - $(1, id, v)$: 代表将 $x[id]$ 的值加上 $v$； - $2$: 代表将所有变量的值乘 $2$； 所有运算在 $(\\bmod \\ 10^4)$ 下执行，提示：模意义下的加减乘运算 - 加：`c = (a + b) % mod`； - 减：`c = (",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4161"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个变量 $x[1 \\sim n]$，初始值都为 0。\n\n依次给出 $m$ 个操作的信息，操作分为 2 种：\n\n- $(1, id, v)$: 代表将 $x[id]$ 的值加上 $v$；\n- $2$: 代表将所有变量的值乘 $2$；\n\n所有运算在 $(\\bmod \\ 10^4)$ 下执行，提示：模意义下的加减乘运算\n\n- 加：`c = (a + b) % mod`；\n- 减：`c = (...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments