{"problem":{"name":"『MdOI R5』Variance","description":{"content":"给定两个长度为 $n$ 的整数序列 $a,b$，满足： - $\\forall i\\in [1,n),a_i\\le a_{i+1},b_i\\le b_{i+1}$。 - $\\forall i\\in [1,n],a_i\\le b_i$。 有一个长度为 $n$ 的实数序列 $c$，满足 $c_i\\in [a_i,b_i]$，求 $c$ 的方差的最大值。 你只需要输出答案乘上 $n^2$ 之后的结果","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8920"},"statements":[{"statement_type":"Markdown","content":"给定两个长度为 $n$ 的整数序列 $a,b$，满足：\n- $\\forall i\\in [1,n),a_i\\le a_{i+1},b_i\\le b_{i+1}$。\n\n- $\\forall i\\in [1,n],a_i\\le b_i$。\n\n有一个长度为 $n$ 的实数序列 $c$，满足 $c_i\\in [a_i,b_i]$，求 $c$ 的方差的最大值。\n\n你只需要输出答案乘上 $n^2$ 之后的结果。容易证明这是一个整数。\n\n### 提示\n\n一个长度为 $n$ 的序列 $a$ 的方差为：$\\dfrac{1}{n}\\sum\\limits_{i=1}^n (a_i-\\overline{a})^2$。其中 $\\overline{a}=\\dfrac{1}{n}\\sum\\limits_{i=1}^n a_i$。\n\n本题的计算过程中可能会涉及到超过 `long long` 范围的数，此时可能需要用到 `__int128` 进行处理。\n\n我们提供了以下代码，它可以用于输出一个 `__int128` 类型的数：\n\n``` cpp\nvoid print(__int128 x)\n{\n\tif(x<0)\n\t{\n\t\tputchar('-');\n\t\tx=-x;\n\t}\n\tif(x<10)\n\t{\n\t\tputchar(x+48);\n\t\treturn;\n\t}\n\tprint(x/10);\n\tputchar(x%10+48);\n}\n```\n\n## Input\n\n第一行，一个整数，表示 $n$。\n\n第二行，$n$ 个整数，表示 $a_1,a_2,\\dots,a_n$。\n\n第三行，$n$ 个整数，表示 $b_1,b_2,\\dots,b_n$。\n\n## Output\n\n共一行，一个整数，表示答案。\n\n[samples]\n\n## Background\n\nSubtask 1~5 为原数据，Subtask 6 为 hack 数据。\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^6$，$1\\le a_i,b_i\\le 10^9$。\n\n$\\operatorname{Subtask} 1(10\\%)$：$n\\le 2\\times 10^3$，$a_i=b_i\\le 10^5$。\n\n$\\operatorname{Subtask} 2(20\\%)$：$n\\le 10$，$a_i,b_i\\le 5$。\n\n$\\operatorname{Subtask} 3(20\\%)$：$n\\le 2\\times 10^3$，$a_i,b_i\\le 10^5$。\n\n$\\operatorname{Subtask} 4(20\\%)$：$n\\le 10^5$，$a_i,b_i\\le 2\\times 10^3$。\n\n$\\operatorname{Subtask} 5(30\\%)$：无特殊限制。\n\n#### 样例说明 1\n\n$c$ 只可能为 $(1,10)$。\n\n#### 样例说明 2\n\n一种最优的 $c$ 为 $(1,2,5)$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8920","tags":["数学","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["2\n1 10\n1 10","81"],["3\n1 2 3\n3 4 5","26"]],"created_at":"2026-03-03 11:09:25"}}