{"problem":{"name":"[USACO24FEB] Quantum Moochanics G","description":{"content":"在空闲时间，Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子，命名为**哞微子**和**反哞微子**。如同标准的[物质-反物质对](https://baike.baidu.com/item/%E5%8F%8D%E7%89%A9%E8%B4%A8/115035)，哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于，每当 Bessie 看向它们时它们就会改变运动方向（同时保","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10195"},"statements":[{"statement_type":"Markdown","content":"在空闲时间，Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子，命名为**哞微子**和**反哞微子**。如同标准的[物质-反物质对](https://baike.baidu.com/item/%E5%8F%8D%E7%89%A9%E8%B4%A8/115035)，哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于，每当 Bessie 看向它们时它们就会改变运动方向（同时保持相同的速率）。\n\n在她最新的实验中，Bessie 将**偶数** $N$（$2\\le N\\le 2\\cdot 10^5$）个这些粒子排成一行。这一行的左端以哞微子开始，然后在两种类型的粒子之间交替，第 $i$ 个粒子位于位置 $p_i$（$0\\le p_1<\\cdots <p_N\\le 10^{18}$）。哞微子初始时**向右**运动而反哞微子初始时**向左**运动，其中第 $i$ 个粒子以每秒 $s_i$ 单位的恒定速率运动（$1\\le s_i\\le 10^9$）。\n\nBessie 在以下时刻进行观察：\n\n- 首先是实验开始后 $1$ 秒。\n- 然后是第一次观察后 $2$ 秒。\n- 然后是第二次观察后 $3$ 秒。\n- $\\ldots \\ldots$\n- 然后是第 $n$ 次观察后 $n+1$ 秒。\n\n在每次观察中，Bessie 都会记下哪些粒子消失了。\n\n这个实验可能需要非常长的时间才能完成，所以 Bessie 想要首先模拟一下它的结果。根据实验设置，请帮助 Bessie 求出她何时（即**观察次数**）会观察到各个粒子消失！可以证明，所有粒子最终都会消失。\n\n## Input\n\n每个测试点包含 $T$（$1\\le T\\le 10$）个独立的测试用例。\n\n每个测试用例包含三行。第一行包含 $N$，第二行包含 $p_1,\\ldots,p_N$，第三行包含 $s_1,\\ldots,s_N$。\n\n输入保证所有 $N$ 之和不超过 $2\\cdot 10^5$。 \n\n## Output\n\n对于每一个测试用例，输出每个粒子消失时的观察次数，用空格分隔。 \n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n对于第一个测试用例，Bessie 在前 $8$ 次观察中观察到以下情况：\n\n- 哞微子（初始时向右运动）出现在位置 $2\\to 0\\to 3\\to −1\\to 4\\to −2\\to 5\\to −3$。\n- 反哞微子（初始时向左运动）出现在位置 $10\\to 12\\to 9\\to 13\\to 8\\to 14\\to 7\\to 15$。\n\n然后恰好在观察 $9$ 时，两个粒子在位置 $6$ 相遇并相互湮灭。\n\n对于第二个测试用例，反哞微子的初始位置更靠右 $1$\n单位，从而两个粒子在观察 $11$ 之前半秒在位置 $6.5$ 相遇。\n\n注意我们只关心观察次数，不关心时刻或位置。\n\n### 样例解释 2\n\n对于第一个测试用例：\n\n- 最左边的两个粒子恰好在观察 $1$ 时在位置 $2$ 相遇。\n- 最右边的两个粒子在观察 $3$ 之前半秒在位置 $6.5$ 相遇。\n\n### 测试点性质\n\n- 测试点 $3$：$N=2$。\n- 测试点 $4$：$N\\le 2000$，且对于所有粒子，$p_i\\le 10^4$。\n- 测试点 $5-7$：$N\\le 2000$。\n- 测试点 $8-12$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10195","tags":["数学","USACO","堆","2024","O2优化"],"sample_group":[["4\n2\n1 11\n1 1\n2\n1 12\n1 1\n2\n1 11\n4 6\n2\n1 11\n4 5","9 9\n11 11\n1 1\n3 3"],["2\n4\n1 3 5 8\n1 1 1 1\n4\n1 4 5 8\n1 1 1 1","1 1 3 3\n7 2 2 7"]],"created_at":"2026-03-03 11:09:25"}}