题目背景

此题为 div.2 B 的 extra sub，并非完整的题，总分为 $25$ 分（进入主题库后满分为 $100$ 分）。

$\text{bh1234666}$ 正在学习二分查找。

题目描述

众所周知二分查找的 $\text{mid}$ 在计算时可以取 $\lfloor\dfrac{l+r}{2}\rfloor$ 或者 $\lceil\dfrac{l+r}{2}\rceil$,于是有选择困难症的 $\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\textit{mid}$。

现在 $\text{bh1234666}$ 告诉你了他要找的数在序列内的下标（从 $0$ 开始，可以理解为在一个 $0\sim n-1$ 的升序序列内查询询问的数），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\textit{cnt}$ 的可能的最终值的最小值）。

循环：

int find(int *num,int x,int len)
{
	int l=0,r=len-1,mid,cnt=0,w;
	while(l<r)
	{
		cnt++;
		w=rand()%2;
		mid=(l+r+w)/2;
		if(num[mid]-w<x) l=mid+!w;
		else r=mid-w;
	}
	return mid;
}

递归：

int cnt;
int get(int *num,int x,int l,int r)
{
	if(l==r) return l;
	cnt++;
	int w=rand()%2;
	int mid=(l+r+w)/2;
	if(num[mid]-w<x) return get(num,x,mid+!w,r);
	else return get(num,x,l,mid-w);
}
int find(int *num,int x,int len)
{
	cnt=0;
	return get(num,x,0,len-1);
}

注：以上两代码完全等价。

输入格式

第一行给出一个整数 $n$ 表示序列长度。

第二行两个整数 $q$，$q_2$ 表示询问的次数，其中 $q$ 表示输入的询问次数，$q_2$ 表示由数据生成器生成的询问次数。

接下来一行 $q$ 个整数表示需要查询的数字。

接下来由数据生成器给出 $q_2$ 个询问（无需读入）。

输出格式

在总共的 $q+q_2$ 次询问中，记第 $i$ 次询问的答案为 $ans_i$。

请你输出一个整数 $\sum\limits_{i=1}^{q+q_2}i\times ans_i$ 来表示答案。

10
3 0
2 6 8

18

13
5 0
0 1 4 6 11

52

1928374
10 1000000
193 3489 238 438 8 912 83 19 12489 10

10000215403302

提示

样例 1 解释

还原后的输出：$3\ 3\ 3$。

找 $2$：

取 $[1,5]$。

取 $[1,3]$。

取 $[3,3]$（退出循环）。

样例 2 解释

还原后的输出：$3\ 4\ 3\ 3\ 4$。

数据生成器

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull sd = 111111111111111111ull, sd2, k = 1;
ull qu, n, ans;//qu表示每次询问的位置。 
inline ull get_q(int i)
{
	sd = (sd2 ^ (sd2 >> 3)) + 998244353;
	return ((sd2 = sd ^ (sd << 37)) & k) + ((i & 1) ? 0 : (n - k - 1));
}
int q, q2;
void init()
{
	//Put your code here or not.
}
inline ull get_ans(ull x)
{
	//Put your code here.
}
int main()
{
	cin >> n;
	sd2 = n;
	while((k << 1) <= n + 1) k <<= 1;
	k -= 1;
	cin >> q >> q2;
	init();
	for(int i = 1; i <= q; i++)
	{
		cin >> qu;
		ans += get_ans(qu) * i;
	}
	for(int i = 1; i <= q2; i++)
	{
		qu = get_q(i);
		ans += get_ans(qu) * (i + q);
	}
	cout << ans << endl;
	return 0;
}

数据范围及约定

此题不进行捆绑测试，分数为各点分数之和。数据存在梯度，如下表所示。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{ExTest} & \textbf{Score} & \textbf{特殊限制} \cr\hline 1 & 5 & n,q_2 \le 2^{20}\cr\hline 2 & 5 & n \le 2^{30},q_2 \le 2\times 10^6 \cr\hline 3 & 5 & n \le 2^{40},q_2 \le 5 \times 10^6 \cr\hline 4 & 5 & n \le 2^{50},q_2 \le 2\times 10^7 \cr\hline 5 & 5 & n \le 2^{60},q_2 \le 2\times 10^8 \cr\hline \end{array} $$

对于 $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$。

本题保证时限是 std 的两倍以上且使用给出的模板可以通过此题。