Çubuq problemləri#1102

Çubuq problemləri (Həll təhlili)

Hər indeks üçün $i$ , $R M in Q (s_{i + 1}, ..., s_{k}) > s_{i}$ RMinQ(s_{i+1}, ..., s_k) > s_i şərti təmin edilən maksimum $k (i \leq k \leq n)$ k~(i \le k \le n) indeksini tapırıq. Bunu ikili axtarışla həyata keçirmək olar. Bundan sonra, tələb olunan indeks $j$ , $i \leq j \leq k$ i \le j \le k olan intervalda $R M a x Q (s_{i}, ..., s_{k})$ RMaxQ(s_i, ..., s_k) dəyərinin çatıldığı mövqe olaraq təyin edilir.

Beləliklə, hər indeks $i$ üçün maksimum mümkün olan indeks $j$ tapılmalıdır və tapılan bütün cütlüklər $(i, j)$ arasında ən böyük fərqi $j - i$ j - i tapırıq.

Nümunə

Üçüncü nümunəni nəzərdən keçirək.

Tutaq ki, $i = 2 (s_{2} = 4)$ i = 2~(s_2 = 4). Burada $R M in Q (s_{i + 1}, ..., s_{k}) > 4$ RMinQ(s_{i+1}, ..., s_k) > 4 şərtini təmin edən $k = 7$ k = 7 maksimum indekdir. $R M a x Q (s_{3}, ..., s_{7})$ RMaxQ(s_3, ..., s_7) dəyəri indeks $j = 6$ j = 6 üzərində əldə edilir.

Alqoritmin həyata keçirilməsi

Daimlər və massivləri elan edirik.

#define MAX 50010
#define LOGMAX 16
int dp_max[MAX][LOGMAX], dp_min[MAX][LOGMAX];
int a[MAX];

Build_RMQ_Array funksiyası sürətli minimum ( $d p_min$ ) və maksimum ( $d p_ma x$ ) sorğular üçün $R M Q$ cədvəllərini qurur:

$d p_min [i] [j]$ dp\_min[i][j] $i$ mövqeyindən başlayaraq uzunluğu $2^{j}$ 2^j olan aralıqdakı minimum dəyəri saxlayır.
$d p_ma x [i] [j]$ dp\_max[i][j] $i$ mövqeyindən başlayaraq uzunluğu $2^{j}$ 2^j olan aralıqdakı maksimum dəyərə malik elementin indeksini saxlayır.

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

  for (j = 1; 1 << j <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
    {
      if (b[dp_max[i][j - 1]] > b[dp_max[i + (1 << (j - 1))][j - 1]])
        dp_max[i][j] = dp_max[i][j - 1];
      else
        dp_max[i][j] = dp_max[i + (1 << (j - 1))][j - 1];

      dp_min[i][j] = 
        min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
    }
}

C++

RangeMaxQuery funksiyası $[i, j]$ aralığındakı maksimum elementin indeksini tapır.

int RangeMaxQuery(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 

  if (a[dp_max[i][k]] > a[dp_max[j - (1<<k) + 1][k]])
    return dp_max[i][k];
  else
    return dp_max[j - (1<<k) + 1][k];
}

C++

RangeMinQuery funksiyası $[i, j]$ aralığında minimum dəyəri tapır.

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

BinSearch funksiyası ikili axtarışla $[L e f t; R i g h t]$ [Left; Right] intervalında $a [L e f t]$ a[Left]-dən böyük olan elementlər $L e f t + 1$ Left + 1 və $k$ arasında olan ən böyük $k$ indeksini tapır.

int BinSearch(int Left, int Right)
{
  int MinValue = a[Left++];
  if (RangeMinQuery(Left,Right) > MinValue) return Right;

  while (Right > Left)
  {
    int Middle = (Left + Right) / 2;
    if (RangeMinQuery(Left,Middle) > MinValue)
      Left = Middle + 1;
    else
      Right = Middle;
  }

  if (dp_min[Left][0] <= MinValue) Left--;
  return Left;
}

C++

Proqramın əsas hissəsi. Ardıcıllıqla testləri işləyirik.

while(scanf("%d",&n) == 1)
{
  for(i = 1; i <= n; i++) scanf("%d",&a[i]);

$R M in Q$ və $R M a x Q$ massivləri qururuq.

  Build_RMQ_Array(a);

Hər indeks $i$ üçün:

$B in S e a r c h (i, n)$ BinSearch(i, n) istifadə edərək, $i + 1$ i + 1 və $k$ aralığında bütün elementlərin $a [i]$ -dən böyük olduğu ən böyük indeksi $k$ tapırıq;
$[i, k]$ aralığında maksimum dəyərin çatıldığı indeks $j$ -ni tapırıq.
$j - i$ j - i ən böyük fərq olduğunu yoxlayırıq.

  res = 0;
  for(i = 1; i <= n; i++)
  {
    k = BinSearch(i, n);
    j = RangeMaxQuery(i,k);
    if (j - i > res) res = j - i;
  }

C++

Cavabı çıxarırıq. Əgər $r es = 0$ res = 0, o zaman $- 1$ çıxarılır.

  if (res == 0) res = -1;
  printf("%d\n",res);
}