{"problem":{"name":"「HGOI-1」Binary search Ex","description":{"content":"众所周知二分查找的 $\\text{mid}$ 在计算时可以取 $\\lfloor\\dfrac{l+r}{2}\\rfloor$ 或者 $\\lceil\\dfrac{l+r}{2}\\rceil$,于是有选择困难症的 $\\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\\textit{mid}$。 现在 $\\text{bh1234666}$ 告诉你了","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8487"},"statements":[{"statement_type":"Markdown","content":"众所周知二分查找的 $\\text{mid}$ 在计算时可以取 $\\lfloor\\dfrac{l+r}{2}\\rfloor$ 或者 $\\lceil\\dfrac{l+r}{2}\\rceil$,于是有选择困难症的 $\\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\\textit{mid}$。\n\n现在 $\\text{bh1234666}$ 告诉你了他要找的数在序列内的下标（从 $0$ 开始，可以理解为在一个 $0\\sim n-1$ 的升序序列内查询询问的数），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\\textit{cnt}$ 的可能的最终值的最小值）。\n\n循环：\n```cpp\nint find(int *num,int x,int len)\n{\n\tint l=0,r=len-1,mid,cnt=0,w;\n\twhile(l<r)\n\t{\n\t\tcnt++;\n\t\tw=rand()%2;\n\t\tmid=(l+r+w)/2;\n\t\tif(num[mid]-w<x) l=mid+!w;\n\t\telse r=mid-w;\n\t}\n\treturn mid;\n}\n```\n递归：\n```\nint cnt;\nint get(int *num,int x,int l,int r)\n{\n\tif(l==r) return l;\n\tcnt++;\n\tint w=rand()%2;\n\tint mid=(l+r+w)/2;\n\tif(num[mid]-w<x) return get(num,x,mid+!w,r);\n\telse return get(num,x,l,mid-w);\n}\nint find(int *num,int x,int len)\n{\n\tcnt=0;\n\treturn get(num,x,0,len-1);\n}\n```\n注：以上两代码完全等价。\n\n## Input\n\n第一行给出一个整数 $n$ 表示序列长度。\n\n第二行两个整数 $q$，$q_2$ 表示询问的次数，其中 $q$ 表示输入的询问次数，$q_2$ 表示由数据生成器生成的询问次数。\n\n接下来一行 $q$ 个整数表示需要查询的数字。\n\n接下来由数据生成器给出 $q_2$ 个询问（无需读入）。\n\n## Output\n\n在总共的 $q+q_2$ 次询问中，记第 $i$ \n次询问的答案为 $ans_i$。\n\n请你输出一个整数 $\\sum\\limits_{i=1}^{q+q_2}i\\times ans_i$ 来表示答案。\n\n[samples]\n\n## Background\n\n此题为 [div.2 B](https://www.luogu.com.cn/problem/P8481) 的 extra sub，并非完整的题，总分为 $25$ 分（进入主题库后满分为 $100$ 分）。\n\n$\\text{bh1234666}$ 正在学习[二分查找](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin)。\n\n## Note\n\n### 样例 1 解释\n\n还原后的输出：$3\\  3\\  3$。\n\n找 $2$：\n\n取 $[1,5]$。\n\n取 $[1,3]$。\n\n取 $[3,3]$（退出循环）。\n\n### 样例 2 解释\n\n还原后的输出：$3\\ 4\\ 3\\  3\\  4$。\n\n#### 数据生成器\n\n```cpp\n#include<bits/stdc++.h>\nusing namespace std;\n#define ull unsigned long long\null sd = 111111111111111111ull, sd2, k = 1;\null qu, n, ans;//qu表示每次询问的位置。 \ninline ull get_q(int i)\n{\n\tsd = (sd2 ^ (sd2 >> 3)) + 998244353;\n\treturn ((sd2 = sd ^ (sd << 37)) & k) + ((i & 1) ? 0 : (n - k - 1));\n}\nint q, q2;\nvoid init()\n{\n\t//Put your code here or not.\n}\ninline ull get_ans(ull x)\n{\n\t//Put your code here.\n}\nint main()\n{\n\tcin >> n;\n\tsd2 = n;\n\twhile((k << 1) <= n + 1) k <<= 1;\n\tk -= 1;\n\tcin >> q >> q2;\n\tinit();\n\tfor(int i = 1; i <= q; i++)\n\t{\n\t\tcin >> qu;\n\t\tans += get_ans(qu) * i;\n\t}\n\tfor(int i = 1; i <= q2; i++)\n\t{\n\t\tqu = get_q(i);\n\t\tans += get_ans(qu) * (i + q);\n\t}\n\tcout << ans << endl;\n\treturn 0;\n}\n```\n\n### 数据范围及约定\n\n此题不进行捆绑测试，分数为各点分数之和。数据存在梯度，如下表所示。\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{ExTest} & \\textbf{Score} & \\textbf{特殊限制} \\cr\\hline\n1 & 5 & n,q_2 \\le 2^{20}\\cr\\hline\n2 & 5 & n \\le 2^{30},q_2 \\le 2\\times 10^6 \\cr\\hline\n3 & 5 & n \\le 2^{40},q_2 \\le 5 \\times 10^6 \\cr\\hline\n4 & 5 &  n \\le 2^{50},q_2 \\le  2\\times 10^7 \\cr\\hline\n5 & 5 &  n \\le 2^{60},q_2 \\le 2\\times 10^8 \\cr\\hline\n\\end{array}\n$$\n对于 $100\\%$ 的数据，$1 \\le n \\le 2^{60}$，$1 \\le q+q_2 \\le n$，$q \\le 2^{20}$，$q_2 \\le 2 \\times 10^8$。\n\n本题保证时限是 std 的两倍以上且使用给出的模板可以通过此题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8487","tags":["数学","二分","洛谷原创","O2优化","位运算","洛谷月赛"],"sample_group":[["10\n3 0\n2 6 8","18"],["13\n5 0\n0 1 4 6 11\n","52"],["1928374\n10 1000000\n193 3489 238 438 8 912 83 19 12489 10","10000215403302"]],"created_at":"2026-03-03 11:09:25"}}