{"problem":{"name":"[北大集训 2021] 随机数据","description":{"content":"有 $n$ 件物品，用 $0, \\cdots, n-1$ 对它们编号，规定物品 $i$ 的价值为 $v_i$。 A 和 B 正在轮流玩一个游戏，该游戏会进行多轮。 每轮开始时，如果所有可用的物品都已经被取走，游戏将立刻结束。否则，A 必须选择一件未被取走的物品，将其取走。 假设 A 取走的物品编号为 $i$。接下来，B 可以选择从物品 $(i - d + n) \\bmod n$ 和物品 $(","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8995"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 件物品，用 $0, \\cdots, n-1$ 对它们编号，规定物品 $i$ 的价值为 $v_i$。\n\nA 和 B 正在轮流玩一个游戏，该游戏会进行多轮。\n\n每轮开始时，如果所有可用的物品都已经被取走，游戏将立刻结束。否则，A 必须选择一件未被取走的物品，将其取走。\n\n假设 A 取走的物品编号为 $i$。接下来，B 可以选择从物品 $(i - d + n) \\bmod n$ 和物品 $(i + d) \\bmod n$ 中选取一件未被取走的物品，将其取走；或者他可以选择跳过本次操作。随后游戏进入到下一轮。特别地，如果这两件物品都已经被取走了，B 只能选择跳过本次操作。\n\nA 和 B 都想最大化自己取走的物品的价值之和，我们假定 A 与 B 都采取了最优策略。\n\n此外，在游戏开始前，有一些物品可能是不可用的。在游戏过程中，不可用的物品将会被忽略，即：A 和 B 都不能取走不可用的物品；当所有可用的物品都已经被取走时，游戏立刻结束。\n\n初始时，所有物品都是可用的。你的程序需要支持 $q$ 次操作，每次操作的内容为：给定一个 $x$，如果物品 $x$ 是不可用的，它将变为可用的；如果它是可用的，它将变为不可用的。每次操作后，你需要回答：假设从当前状态开始游戏，游戏结束时 B 取走的物品的价值之和。\n\n不幸的是，这是一道 IO 题，**物品的数量可能会达到 $10^{16}$**。身为一个 OIer，你无法处理如此大规模的数据，因此 $v_i$ 将会用一种**特殊的方法**生成：给定一个长度为 $m$ 的数组 $w$，$v_i = w_{i \\bmod m}$。\n\n## Input\n\n输入的第一行包含四个**正整数** $n, d, m, q$，保证 $1 < n \\le 10^{16}, 1\\le d < n, 1 \\le m \\le 2\\times 10^4, q \\le 10^5$。\n\n输入的第二行包含 $m$ 个整数，第 $i$ 个整数表示 $w_{i-1}$ 的值，保证 $1 \\le w_i \\le 400$。\n\n接下来的 $q$ 行，每行包含一个整数 $x$，表示一次对物品 $x$ 的操作。保证 $0 \\le x < n$。\n\n## Output\n\n输出 $q$ 行，每行一个整数，对应一次操作之后的答案。\n\n[samples]\n\n## Background\n\nCTT2021 D4T3\n\n## Note\n\nSubtask 1 (5 pts) : $n \\le 20, q = 1$\n\nSubtask 2 (10 pts) : $n \\le 10^5, q = 1$\n\nSubtask 3 (15 pts) : $n, q \\le 10^5$\n\nSubtask 4 (30 pts) : $q = 1$\n\nSubtask 5 (40 pts) : 无特殊限制。\n\n如有需要，可以使用 `__int128` 处理 `long long` 乘法取模，下面是一个使用 `__int128` 计算 $a \\times b \\bmod m$ 的例子：\n\n```cpp\nlong long a = 1e15;\nlong long b = 1e15;\nlong long m = 12345678910;\nlong long c = ((__int128) a * b) % m;\n```","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8995","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["5 2 3 2\n1 3 2\n1\n1\n","3\n4\n"],["10 4 5 5\n40 355 190 215 161\n3\n4\n0\n3\n4\n","581\n460\n420\n541\n702\n"]],"created_at":"2026-03-03 11:09:25"}}