{"problem":{"name":"[蓝桥杯 2021 国 A] 冰山","description":{"content":"一片海域上有一些冰山，第 $i$ 座冰山的体积为 $V_{i}$ 。 随着气温的变化，冰山的体积可能增大或缩小。第 $i$ 天, 每座冰山的变化量都是 $X_{i}$。当 $X_{i}>0$ 时，所有冰山体积增加 $X_{i}$；当 $X_{i}<0$ 时，所有冰山体积减少 $-X_{i}$；当 $X_{i}=0$ 时，所有冰山体积不变。 如果第 $i$ 天某座冰山的体积变化后小于等于 $0$","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":"LGP8767"},"statements":[{"statement_type":"Markdown","content":"一片海域上有一些冰山，第 $i$ 座冰山的体积为 $V_{i}$ 。\n\n随着气温的变化，冰山的体积可能增大或缩小。第 $i$ 天, 每座冰山的变化量都是 $X_{i}$。当 $X_{i}>0$ 时，所有冰山体积增加 $X_{i}$；当 $X_{i}<0$ 时，所有冰山体积减少 $-X_{i}$；当 $X_{i}=0$ 时，所有冰山体积不变。\n\n如果第 $i$ 天某座冰山的体积变化后小于等于 $0$，则冰山会永远消失。\n\n冰山有大小限制 $k$。如果第 $i$ 天某座冰山 $j$ 的体积变化后 $V_{j}$ 大于 $k$，则它会分裂成一个体积为 $k$ 的冰山和 $V_{j}-k$ 座体积为 $1$ 的冰山。\n\n第 $i$ 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为 $Y_{i}$ 的冰山（$Y_{i}=0$ 表示没有冰山漂来）。\n\n小蓝在连续的 $m$ 天对这片海域进行了观察，并准确记录了冰山的变化。小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。\n\n由于答案可能很大，请输出答案除以 $998244353$ 的余数。\n\n## Input\n\n输入的第一行包含三个整数 $n, m, k$, 分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。\n\n第二行包含 $n$ 个整数 $V_{1}, V_{2}, \\cdots, V_{n}$，表示初始时每座冰山的体积。\n\n接下来 $m$ 行描述观察的 $m$ 天的冰山变化。其中第 $i$ 行包含两个整数 $X_{i}, Y_{i}$，意义如前所述。\n\n## Output\n\n输出 $m$ 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 $998244353$ 的余数。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n在本样例说明中，用 $\\left[a_{1}, a_{2}, \\cdots, a_{n}\\right]$ 来表示每座冰山的体积。\n\n初始时的冰山为 $[1]$。\n\n第 $1$ 天结束时，有 $3$ 座冰山：$[1,1,6]$。\n\n第 $2$ 天结束时，有 $6$ 座冰山：$[1,1,2,3,3,6]$。\n\n第 $3$ 天结束时，有 $5$ 座冰山：$[1,1,2,2,5]$。\n\n**【评测用例规模与约定】**\n\n对于 $40 \\%$ 的评测用例，$n, m, k \\leq 2000$;\n\n对于 $60 \\%$ 的评测用例，$n, m, k \\leq 20000$;\n\n对于所有评测用例，$1 \\leq n, m \\leq 10^5,1 \\leq k \\leq 10^{9}, 1 \\leq V_{i} \\leq k, 0 \\leq Y_{i} \\leq k, -k \\leq X_{i} \\leq k$。 \n\n蓝桥杯 2021 国赛 A 组 G 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8767","tags":["模拟","堆","2021","蓝桥杯国赛"],"sample_group":[["1 3 6\n1\n6 1\n2 2\n-1 1","8\n16\n11"]],"created_at":"2026-03-03 11:09:25"}}