Background

This problem is an extra subtask of div.2 B. It is not a full problem. The total score is $25$ points (after entering the main problem set, the full score is $100$ points).

$\text{bh1234666}$ is learning binary search.

Problem Description

As everyone knows, when computing $\text{mid}$ in binary search, you can take either $\lfloor\dfrac{l+r}{2}\rfloor$ or $\lceil\dfrac{l+r}{2}\rceil$. So the indecisive student $\text{bh1234666}$ added randomness into his binary search code: each time, he randomly chooses one of them as $\textit{mid}$.

Now $\text{bh1234666}$ tells you the index (starting from $0$) of the number he wants to find in the sequence (you can think of it as querying a number in an increasing sequence of indices $0 \sim n-1$). He wants to know, in the best possible luck, how many times the loop needs to run (that is, the minimum possible final value of $\textit{cnt}$ in the code).

Loop:

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;
}

Recursion:

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);
}

Note: the two codes above are completely equivalent.

Input Format

The first line gives an integer $n$ indicating the length of the sequence.

The second line gives two integers $q$, $q_2$, indicating the number of queries, where $q$ is the number of queries given in the input, and $q_2$ is the number of queries generated by the data generator.

The next line contains $q$ integers, indicating the numbers to query.

Then the data generator provides $q_2$ queries (no need to read them).

Output Format

Among the total of $q+q_2$ queries, let the answer to the $i$-th query be $ans_i$.

Output an integer $\sum\limits_{i=1}^{q+q_2}i\times ans_i$ as the result.

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

Hint

Explanation of Sample 1

The restored output is: $3\ 3\ 3$.

Find $2$:

Take $[1,5]$.

Take $[1,3]$.

Take $[3,3]$ (exit the loop).

Explanation of Sample 2

The restored output is: $3\ 4\ 3\ 3\ 4$.

Data Generator

#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;
}

Constraints and Notes

This problem does not use bundled test. The score is the sum of the scores of all subtasks. The testdata has multiple levels, as shown in the table below.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{ExTest} & \textbf{Score} & \textbf{Special Limits} \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}$$

For $100\%$ of the data, $1 \le n \le 2^{60}$, $1 \le q+q_2 \le n$, $q \le 2^{20}$, and $q_2 \le 2 \times 10^8$.

This problem guarantees that the time limit is more than twice the standard one, and using the provided template can pass this problem.

Translated by ChatGPT 5