Permutation#4079

Permutation (Editorial)

Let the array $b$ contain the original permutation. Construct an array $a$ such that:

a [x] = t h e p os i t i o n o f t h e n u mb er x in a r r a y b

a[x] = the~position~of~the~number~x~in~array~b

For example, if

then

The answer to a query $(u, v)$ is $a [R M Q a [u .. v]]$ a[RMQa[u..v]].

Example

Consider the input permutation given by array $b$ , and construct the auxiliary array $a$ based on it.

For example, the number $1$ is located at position $9$ in the permutation (that is, $b [9] = 1$ b[9] = 1). Therefore, we set $a [1] = 9$ a[1] = 9.

Now consider the query $(a, b) = (2, 4)$ (a, b) = (2, 4). The number $2$ is at position $4$ , the number $3$ is at position $10$ , and the number $4$ is at position $7$ . Thus, in array $a$ , the elements with indices $2, 3$ , and $4$ are equal to $4, 10$ , and $7$ respectively — these are the positions of the numbers $2, 3$ , and $4$ in the original array $b$ .

It remains to find the minimum value in the subarray $a [2..4]$ . It is equal to $4$ (the minimum among $4, 10$ and $7$ ). Therefore, the answer is position $4$ .

Algorithm implementation

Declare an array $ma s$ , where $ma s [i] [j]$ mas[i][j] will store the index of the minimum element on the segment $(i, ..., i + 2^{j} - 1)$ (i, ..., i + 2^j - 1). Declare auxiliary arrays $a$ and $b$ .

#define DIM1 100010
#define DIM2 17
int mas[DIM1][DIM2];
int a[DIM1], b[DIM1];

The function Build_RMQ_Array constructs the array $ma s$ based on the array $b$ in such a way that

ma s [i] [j] = min (b_{i}, b_{i + 1}, ..., b_{i + 2^{j}})

mas[i][j] = min(b_i, b_{i+1}, ..., b_{i+2^j})

void Build_RMQ_Array(int *b)
{
  int i, j;
  for (i = 1; i <= n; i++) mas[i][0] = b[i];
  for (j = 1; 1 << j <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = min(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

C++

The function RMQ returns the minimum value on the segment $(b_{i}, b_{i + 1}, ..., b_{j})$ (b_i, b_{i+1}, ..., b_j) in $O (1)$ time.

int RMQ(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 
  return min(mas[i][k],mas[j - (1<<k) + 1][k]);
}

Read the input data and store the permutation in the array $b$ .

scanf("%d %d",&n,&q);
for (i = 1; i <= n; i++) scanf("%d",&b[i]);

Build the array $a$ .

for (i = 1; i <= n; i++) a[b[i]] = i;

Perform preprocessing to support $R M Q$ queries.

Build_RMQ_Array(a);

For each query $(u, v)$ compute and print the answer.

for (i = 0; i < q; i++)
{
  scanf("%d %d",&u,&v);
  printf("%d\n",RMQ(u,v));
}

Java implementation

import java.util.*;

public class Main
{
  private final static int DIM1 = 100010;
  private final static int DIM2 = 17;
  static int[] a = new int[DIM1];    
  static int[] b = new int[DIM1];    
  static int[][] mas = new int[DIM1][DIM2];
  
  static int min(int a, int b)
  {
    return (a < b) ? a : b;
  }
  
  static void Build_RMQ_Array(int[] b, int n)
  {
    int i, j;
    for (i = 1; i <= n; i++) mas[i][0] = b[i];
    for (j = 1; 1 << j <= n; j++)
      for (i = 1; i + (1 << j) - 1 <= n; i++)
        mas[i][j] = 
          min(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
  }

  static int RMQ(int i, int j)
  {
    int k = 0;
    while ((1 << (k + 1)) <= j - i + 1) k++; 
    return min(mas[i][k],mas[j - (1<<k) + 1][k]);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int i, n = con.nextInt(), 
           q = con.nextInt();
    for (i = 1; i <= n; i++) b[i] = con.nextInt();
    for (i = 1; i <= n; i++) a[b[i]] = i;
    
    Build_RMQ_Array(a, n);

    for(i = 0; i < q; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      System.out.println(RMQ(u,v));
    }
  }
}

Java