{"problem":{"name":"「Wdoi-2」来自地上的支援","description":{"content":"### 简要题意 给定正整数 $n$、$v$ 和长度为 $n$ 的数组 $\\{A_i\\}$。 有一个长度为 $n$ 的数组 $B$，初始值与 $A$ 相同。  执行 $n$ 次操作，第 $i$ 次操作在 $[1,i]$ 中按如下规则选取一个正整数 $j$，然后把 $B_j$ 变成 $B_j+v$： - 选取 $B_j$ 最大的 $j$。 - $B_j$ 相同时选择 $A_j$ 最大的 $j$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8539"},"statements":[{"statement_type":"Markdown","content":"### 简要题意\n给定正整数 $n$、$v$ 和长度为 $n$ 的数组 $\\{A_i\\}$。\n\n有一个长度为 $n$ 的数组 $B$，初始值与 $A$ 相同。 \n执行 $n$ 次操作，第 $i$ 次操作在 $[1,i]$ 中按如下规则选取一个正整数 $j$，然后把 $B_j$ 变成 $B_j+v$：\n- 选取 $B_j$ 最大的 $j$。\n- $B_j$ 相同时选择 $A_j$ 最大的 $j$。\n- $A_j,B_j$ 均相同，选择较小的 $j$。\n\n我们称这是选中了一次 $j$。\n\n有 $m$ 次询问，每次询问给定 $x_i,k_i$。表示求最小的 $s$，使得**若**将 $A_{x_i}$ 的初始值改为 $s$（注意此时 $B_{x_i}$ 的初始值也会跟着改变），$x_i$ 至少被选中 $k_i$ 次，或报告不存在（**结果为** $0$）。请注意，$s$ 不存在最小值时也是报告不存在（**结果为** $0$）。\n\n询问之间互相独立，也就是每次询问不会对 $A_{x_i}$ 和 $B_{x_i}$ 产生实质性更改。\n\n### 原始题意\n\n到达控制中心之后，主角组和灵乌路空进行了激烈的狗斗大赛。负责技术维护的河童需要接受荷取来自地上指挥部的指令，保障生产安全。\n\n具体地，有 $n$ 个核反应机组依次排开，第 $i$ 个机组的活动强度为 $A_i$。为了维护平衡，控制系统依次操作 $n$ 次，第 $i$ 次操作会在前 $i$ 个机组中找到一个**当前活动度最高的**机组，进行一次调节平衡操作，并将其活动度增加 $v$。倘若有多个机组活动度最高，就应当选择初始活动度**最大**的，若还是无法比较，则取编号最小。\n\n为了在自动控制系统的基础上调节平衡，荷取会发出 $m$ 条指令，形如她每次会给出两个整数 $x_i,k_i$，表示她会修改第 $x_i$ 个机组的初始活动度。她希望通过修改（必须改成一个**非负整数** $s$）后，$x_i$ 号机组至少被平衡 $k_i$ 次。如果无论如何都无法达到要求，那么结果就是 $0$；否则请求出满足条件的**最小的** $s$。\n\n## Input\n\n- 第一行有三个整数 $n, m, v$。\n- 接下来一行，有 $n$ 个整数，描述 $a_i$。\n- 接下来 $m$ 行，每行有两个整数 $x_i,k_i$，描述一次询问。\n\n## Output\n\n- 一行，输出两个整数，表示所有结果的**异或和**与**加法和**。\n\n[samples]\n\n## Background\n\n波光粼粼的山顶湖与庄严神圣的神社之下，是一座复合型活火山。  \n沿幻想风穴而下，便能到达火山之下，废弃已久的地狱原址。   \n>在旧地狱中，有一座大都市。那里是旧地狱还是地狱的时候在那工作的众鬼们居住的地方，只有那里亡者们是无法踏入去的。后来地狱体制改革，机构搬离了这个地方。  \n因为这个缘故这块地狱变成了废墟，但却有一部分看上了那里的妖怪擅作主张占领了那里，于是就成了如今的旧地狱了。\n这里比地上更没有秩序可言。悍匪恶霸，特别是惹人类讨厌的家伙都喜欢搬到这边定居下来。\n\n自旧地狱喷泻而出的间歇泉，给妖怪之山带来了优良的温泉，也喷出了大量的怨灵。\n\n为了解决这次异变，乐园的巫女和普通的魔法使结伴而行，在来自地上的支援下，自幻想风穴直冲地底。\n\n先后结（bao）识（da）了黑暗洞窟中的明亮之网、地壳下的嫉妒心、人们所谈论的怪力乱神后，二人来到了遗址中心的洋馆，地灵殿。\n\n受这里主人的指引，二人来到了位于深处的间歇泉地下中心。\n\n## Note\n\n### 样例 1 解释\n\n对于第一次询问，我们将 $A_3$ 修改为 $7$。\n\n- 第一次操作选择了位置 $1$，于是 $B_1$ 变为 $4$。\n- 第二次操作选择了位置 $2$，于是 $B_2$ 变为 $7$。虽然操作前 $B_1=B_2$，但是 $A_2>A_1$，因此选择位置 $2$。\n- 第三次操作选择了位置 $3$，于是 $B_3$ 变为 $10$。\n- 第四次操作选择了位置 $3$，于是 $B_3$ 变为 $13$。\n- 第五次操作选择了位置 $3$，于是 $B_3$ 变为 $16$。\n- 第六次操作选择了位置 $3$，于是 $B_3$ 变为 $19$。\n- 第七次操作选择了位置 $3$，于是 $B_3$ 变为 $22$。\n\n于是位置 $3$ 一共被选择了 $5$ 次，满足题意。可以证明，如果把 $A_3$ 的初始值设为 $6$，无法达成要求。于是该询问结果为 $7$。\n\n对于第二个询问，容易发现不可能有 $4$ 次以上操作选择位置 $6$。因此该询问结果为 $0$。\n\n$7\\oplus 0=7$，$7+0=7$，因此输出 $7,7$。\n\n### 数据范围\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{n,m\\le} & \\bm {a_i\\le } & \\bm{v\\le} & \\textbf{分值} \\cr\\hline\n1 & 10 & 100 & 10 & 10 \\cr\\hline\n2 & 100 & 5\\times 10^3 & 50 & 20 \\cr\\hline\n3 & 10^3 & 10^9 & 100 & 10 \\cr\\hline\n4 & 10^5 & 10^9 & 100 & 25 \\cr\\hline\n5 & 2\\times 10^6 & 10^9 & 100 & 35 \\cr\\hline\n\\end{array}$$\n\n对于全部数据，满足 $1 \\le n,m \\le 2\\times 10^6$，$1 \\le v \\le 100$，$1 \\le a_i \\le 10 ^ 9$，$1 \\le x,k \\le n$。\n\n**本题 IO 量较大，请选择合适的输入方式。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8539","tags":["贪心","线段树","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["7 2 3\n1 4 1 5 4 1 1\n3 3\n6 4","7 7"],["10 10 9\n14 91 84 13 97 92 23 64 31 10 \n5 2\n5 5\n9 1\n2 6\n9 1\n5 4\n3 5\n2 8\n8 2\n5 4\n","245 1177\n"]],"created_at":"2026-03-03 11:09:25"}}