Sparse Tables (Editorial)

The problem requires repeatedly finding the minimum on a segment of an array that does not change after generation. The number of queries reaches $1 0^{7}$ 10^7, so each query must be processed in $O (1)$ . To do this, we use a sparse table — a static data structure for the RMQ (Range Minimum Query) problem.

Building the table. For each position $i$ and each $j$ such that $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n, the cell $ma s [i] [j]$ mas[i][j] stores the index of the minimum element on the segment $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] of length $2^{j}$ 2^j. For $j = 0$ j = 0 the segment consists of one element, so $ma s [i] [0] = i$ mas[i][0] = i.

For $j > 0$ j > 0, split the segment of length $2^{j}$ 2^j into two halves of length $2^{j - 1}$ 2^{j-1}: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] and $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. The indices of the minimums on the halves have already been computed — they are $ma s [i] [j - 1]$ mas[i][j - 1] and $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1]:

The minimum of the whole segment equals the smaller of the two minimums of the halves. Therefore, $ma s [i] [j]$ mas[i][j] equals whichever of the indices $ma s [i] [j - 1]$ mas[i][j - 1] and $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] points to the smaller array element. The table is filled in increasing order of $j$ and contains $O (n lo g n)$ O(n \log n) cells.

Answering a query. Suppose we need to find the minimum on the segment $[u; v]$ . Let $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor be the exponent of the largest power of two not exceeding the length of the segment. The segment of length $2^{k}$ 2^k starting at $u$ and the segment of length $2^{k}$ 2^k ending at $v$ together completely cover $[u; v]$ , since $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

These segments may overlap, but this does not matter for the minimum: an element counted twice does not change the result (unlike, for example, the sum). Therefore, the minimum on $[u; v]$ equals the smaller of the elements $a [ma s [u] [k]]$ a[mas[u][k]] and $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]], and a query is processed in $O (1)$ .

The bounds $u$ and $v$ of the generated queries may come in any order, so before executing a query we swap them if necessary.

Complexity. Building the table takes $O (n lo g n)$ O(n \log n), and each query takes $O (1)$ . The overall complexity is $O (n lo g n + m)$ O(n \log n + m). With $m \leq 1 0^{7}$ m \le 10^7, it is precisely the $O (1)$ query time that makes it possible to fit into the time limit.

Example

Consider the example: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. The generated array coincides with the array given in the problem statement. The table $ma s$ for it is shown below. The cells contain the indices of the minimum elements; a dash means that the segment goes beyond the array.

$j ∖ i$ \boldsymbol{j \setminus i}	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$	$1$	$2$	$3$	$5$	$5$	$6$	$8$	$8$	$10$	—
$2$	$1$	$2$	$5$	$5$	$8$	$8$	$8$	—	—	—
$3$	$1$	$2$	$8$	—	—	—	—	—	—	—

For example, $ma s [3] [2] = 5$ mas[3][2] = 5: on the segment $[3; 6]$ , the minimum element is $a_{5} = 1565158$ a_5 = 1565158. The value $ma s [2] [3] = 2$ mas[2][3] = 2 is obtained from $ma s [2] [2] = 2$ mas[2][2] = 2 and $ma s [6] [2] = 8$ mas[6][2] = 8, since $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265.

The first query: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. The length of the segment is $7$ , so $k = 2$ k = 2. The segment $[3; 9]$ is covered by the segments $[3; 6]$ and $[6; 9]$ , for which $ma s [3] [2] = 5$ mas[3][2] = 5 and $ma s [6] [2] = 8$ mas[6][2] = 8. Since $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158, the answer is $an s_{1} = 570265$ ans_1 = 570265.

The parameters of the second query:

u_{2} = ((17 \cdot 3 + 751 + 570265 + 2) mod 10) + 1 = 10, v_{2} = ((13 \cdot 9 + 593 + 570265 + 5) mod 10) + 1 = 1.

u_2 = ((17 \cdot 3 + 751 + 570265 + 2) \bmod 10) + 1 = 10, \\ v_2 = ((13 \cdot 9 + 593 + 570265 + 5) \bmod 10) + 1 = 1.

Since $u_{2} > v_{2}$ u_2 > v_2, the bounds are swapped, and the minimum on the segment $[1; 10]$ is computed.

All queries are listed in the table:

$i$	$u_{i}$ \boldsymbol{u_i}	$v_{i}$ \boldsymbol{v_i}	segment	$an s_{i}$ \boldsymbol{ans_i}
$1$	$3$	$9$	$[3; 9]$	$570265$
$2$	$10$	$1$	$[1; 10]$	$12345$
$3$	$1$	$2$	$[1; 2]$	$12345$
$4$	$10$	$10$	$[10; 10]$	$1325095$
$5$	$5$	$9$	$[5; 9]$	$570265$
$6$	$2$	$1$	$[1; 2]$	$12345$
$7$	$3$	$2$	$[2; 3]$	$305498$
$8$	$5$	$3$	$[3; 5]$	$1565158$

The last query has the parameters $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3, and its answer is $an s_{8} = 1565158$ ans_8 = 1565158. These are exactly the values that are printed. Note that the original values $u_{8}$ u_8 and $v_{8}$ v_8 are printed, not the ordered bounds of the segment.

Algorithm implementation

The elements of the array $a$ ( $n \leq 1 0^{5}$ n \le 10^5) are stored starting from index $1$ . The sparse table is stored in the array $ma s$ : $ma s [i] [j]$ mas[i][j] is the index of the minimum element on the segment $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1]. Since $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, the values of $j$ do not exceed $16$ , so $L O GM A X = 17$ LOGMAX = 17 is enough for the second dimension.

#define MAX 100001
#define LOGMAX 17
int a[MAX];
int mas[MAX][LOGMAX];

The function check swaps the values of $u$ and $v$ if $u > v$ u > v, so that $u \leq v$ u \le v. The parameters are passed by reference.

void check(int &u, int &v)
{
  int temp;
  if (u > v) temp = u, u = v, v = temp;
}

The function RMQ_nlogn builds the sparse table.

void RMQ_nlogn(void)
{
  int i, j;

First, $ma s [i] [0] = i$ mas[i][0] = i for all $i$ .

  for (i = 1; i <= n; i++) mas[i][0] = i;

Then, for each $j$ while $2^{j} \leq n$ 2^j \le n, and for each $i$ such that the segment $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] does not go beyond the array, choose from $ma s [i] [j - 1]$ mas[i][j - 1] and $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] the index of the smaller element.

  for (j = 1; (1 << j) <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
      if (a[mas[i][j - 1]] < a[mas[i + (1 << (j - 1))][j - 1]])
         mas[i][j] = mas[i][j - 1];
      else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];
}

The function q returns the index of the minimum element on the segment $[i; j]$ . Compute $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor and compare the minimums of two segments of length $2^{k}$ 2^k: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] and $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

int q(int i, int j)
{
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}

C++

The main part of the program. Read $n$ , $m$ , the first array element $a_{1}$ a_1, and the parameters of the first query $u$ and $v$ .

scanf("%d %d",&n,&m);
scanf("%d %d %d",&a[1],&u,&v);

Generate the elements $a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n using the formula from the problem statement. The product $23 \cdot a_{i}$ 23 \cdot a_i does not exceed $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8 and fits into the $in t$ type.

for(i = 2; i <= n; i++)
  a[i] = (23 * a[i-1] + 21563) % 16714589;

Build the sparse table $ma s$ .

RMQ_nlogn();

Process the $m$ queries one by one.

for (i = 1; i <= m; i++)
{

Copy the bounds of the current query into $u 1$ and $v 1$ and, if necessary, order them with the function check. The values $u$ and $v$ themselves are not changed: the parameters of the next query are computed from them, and they are what is printed in the answer.

  u1 = u; v1 = v; check(u1,v1);

Find the minimum element on the segment $[u 1; v 1]$ [u1; v1].

  ans = a[q(u1,v1)];

If the query is not the last one, compute the parameters of the next query using the formulas from the problem statement.

  if (i < m)
  {
    u = ((17*u + 751 + ans + 2*i) % n) + 1;
    v = ((13*v + 593 + ans + 5*i) % n) + 1;
  }
}

Print the parameters of the last query and its answer.

printf("%d %d %d\n",u,v,ans);