{"problem":{"name":"[IOI 2021] 地牢游戏","description":{"content":"Robert 正在设计一款新的电脑游戏。游戏中有一位英雄、$n$ 个敌人和 $n + 1$ 个地牢。敌人从 $0$ 到 $n - 1$ 编号，地牢从 $0$ 到 $n$ 编号。敌人 $i$（$0 \\le i \\le n - 1$）处在地牢 $i$，其能力值为 $s[i]$。地牢 $n$ 里没有敌人。 英雄一开始进入地牢 $x$，初始能力值为 $z$。每次英雄进入地牢 $i$（$0 \\le i \\","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":2048000},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8522"},"statements":[{"statement_type":"Markdown","content":"Robert 正在设计一款新的电脑游戏。游戏中有一位英雄、$n$ 个敌人和 $n + 1$ 个地牢。敌人从 $0$ 到 $n - 1$ 编号，地牢从 $0$ 到 $n$ 编号。敌人 $i$（$0 \\le i \\le n - 1$）处在地牢 $i$，其能力值为 $s[i]$。地牢 $n$ 里没有敌人。\n\n英雄一开始进入地牢 $x$，初始能力值为 $z$。每次英雄进入地牢 $i$（$0 \\le i \\le n - 1$）时，都需要面对敌人 $i$，且会发生以下情况中的一种：\n\n如果英雄的能力值大于等于敌人 $i$ 的能力值 $s[i]$，那么英雄会胜出。这使得英雄的能力值增加 $s[i]$（$s[i] \\ge 1$）。这种情况下，下一步英雄将会进入地牢 $w[i]$（$w[i] > i$）。\n\n否则英雄会战败，这使得英雄的能力值增加 $p[i]$（$p[i] \\ge 1$）。在这种情况下，下一步英雄将会进入地牢 $l[i]$。\n\n注意 $p[i]$ 可能会小于、等于、大于 $s[i]$，$l[i]$ 可能会小于、等于、大于 $i$。无论对战结果如何，敌人 $i$ 始终处在地牢 $i$，且能力值为 $s[i]$。\n\n当英雄进入地牢 $n$ 的时候，游戏结束。可以看出无论英雄的起始地牢和初始能力值如何，游戏一定会在有限次对战之后结束。\n\nRobert 希望你通过 $q$ 次模拟来对游戏进行测试。对于每次模拟，Robert 输入英雄的起始地牢 $x$ 和初始能力值 $z$。你需要做的是对于每次模拟给出游戏结束时英雄的能力值。\n\n## Input\n\n你要实现以下函数：\n```cpp\nvoid init(int n, int[] s, int[] p, int[] w, int[] l)\n```\n- $n$：敌人的数量。\n$s$、$p$、$w$、$l$：长度为 $n$ 的序列。对于每一个 $i$（$0 \\le i \\le n - 1$）：\n  + $s[i]$ 是敌人 $i$ 的能力值，也是击败敌人 $i$ 后英雄增加的能力值。\n  + $p[i]$ 是英雄被敌人 $i$ 击败后增加的能力值。\n  + $w[i]$ 是英雄击败敌人 $i$ 后进入的下一个地牢的编号。\n  + $l[i]$ 是英雄被敌人 $i$ 击败后进入的下一个地牢的编号。\n- 恰好调用此函数一次，且发生在任何对如下的 simulate 函数的调用之前。\n```cpp\nint64 simulate(int x, int z)\n```\n- $x$：英雄的起始地牢编号。\n- $z$：英雄的初始能力值。\n- 假设英雄的起始地牢编号为 $x$，初始能力值为 $z$，函数的返回值是相应情况下游戏结束时英雄的能力值。\n- 恰好调用此函数 $q$ 次。\n\n## Background\n\n**滥用本题评测将被封号**\n\n**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**\n\n这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。\n\n[samples]\n\n## Note\n\n对于所有数据：\n\n- $1 \\le n \\le 400 \\, 000$\n- $1 \\le q \\le 50 \\, 000$\n- $1 \\le s[i], p[i] \\le {10}^7$（对于所有的 $0 \\le i \\le n - 1$）\n- $0 \\le l[i], w[i] \\le n$（对于所有的 $0 \\le i \\le n - 1$）\n- $w[i] > i$（对于所有的 $0 \\le i \\le n - 1$）\n- $0 \\le x \\le n - 1$\n- $1 \\le z \\le {10}^7$\n\n子任务\t|分值|特殊限制\n:-:|:-:|:-:\n$0$|$0$|样例\n$1$|\t$11$|\t$n \\le 50 \\, 000$，$q \\le 100$，$s[i], p[i] \\le 10 \\, 000$（对于所有的 $0 \\le i \\le n - 1$）\n$2$|\t$26$|\t$s[i] = p[i]$（对于所有的 $0 \\le i \\le n - 1$）\n$3$|\t$13$|\t$n \\le 50 \\, 000$，所有的敌人拥有相同的能力值，即 $s[i] = s[j]$，对于所有的 $0 \\le i, j \\le n - 1$\n$4$|\t$12$|\t$n \\le 50 \\, 000$，所有的 $s[i]$ 至多有 $5$ 种不同的数值\n$5$|\t$27$|\t$n \\le 50 \\, 000$\n$6$|\t$11$|\t没有额外的约束条件","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8522","tags":["倍增","2021","IOI","交互题"],"sample_group":[["3 2\n2 6 9\n3 1 2\n2 2 3\n1 0 1\n0 1\n2 3","24\n25"]],"created_at":"2026-03-03 11:09:25"}}