Maksimum (Həll təhlili)

Məsələ aralıq maksimum sorğularına cavab verməyi tələb edir. Massivin elementləri dəyişmir, ona görə də statik data strukturu uyğundur. Sorğuların sayı $5 \cdot 1 0^{5}$ 5 \cdot 10^5-ə çatır, massivin uzunluğu isə $1 0^{5}$ 10^5-dir. Hər seqmentin maksimumunu birbaşa hesablamaq $5 \cdot 1 0^{10}$ 5 \cdot 10^{10}-a qədər əməliyyat tələb edərdi ki, bu da çox yavaşdır.

Biz RMQ məsələsi üçün sparse table-dan istifadə edirik, lakin minimum əvəzinə maksimumu axtarırıq (Range Maximum Query). Maksimum, minimum kimi, hər hansı elementin iki dəfə sayılması halında dəyişmir. Ona görə də sorğu seqmenti $2^{k}$ 2^k uzunluqlu iki üst-üstə düşən seqmentlə örtülə bilər, və onların maksimumlarının böyüyü seçilir.

Cədvəlin bir xanası ya maksimum elementin indeksini, ya da maksimumun özünü saxlaya bilər. Məsələ yalnız dəyəri çap etməyi tələb edir, ona görə də yalnız maksimumu saxlamaq kifayətdir. İndeks variantı maksimumun mövqeyinin məlum olması lazım olduqda lazımdır. Hər iki tətbiq aşağıda verilmişdir.

Məsələnin şərtinə görə, $1 \leq l, r \leq n$ 1 \le l, r \le n, və $l \leq r$ l \le r olması təmin edilmir. Ona görə də sorğunu icra etməzdən əvvəl sərhədləri lazım olduqda dəyişirik.

Mürəkkəblik. Sparse table-ın qurulması $O (n lo g n)$ O(n \log n) vaxt alır, hər sorğu isə $O (1)$ vaxt alır. Ümumi mürəkkəblik $O (n lo g n + q)$ O(n \log n + q)-dır.

Misal

Misaldakı massivi nəzərdən keçirək: $(5, 1, 2, 8, 7, 6, 10, 7, 5, 6)$ (5, 1, 2, 8, 7, 6, 10, 7, 5, 6). $ma s [i] [j]$ mas[i][j]-nin $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmentindəki maksimum olduğu $ma s$ cədvəli aşağıda göstərilmişdir. Tire işarəsi seqmentin massivdən kənara çıxdığını bildirir.

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

Məsələn, $ma s [4] [2] = max (ma s [4] [1], ma s [6] [1]) = max (8, 10) = 10$ mas[4][2] = \max(mas[4][1], mas[6][1]) = \max(8, 10) = 10 — bu $[4; 7]$ seqmentindəki maksimumdur.

$26$ sorğusunu nəzərdən keçirək. Seqmentin uzunluğu $5$ -dir, $5$ -dən böyük olmayan ən böyük ikinin qüvvəti $4$ -dür, ona görə $k = 2$ k = 2. $[2; 6]$ seqmenti $[2; 5]$ və $[3; 6]$ seqmentləri ilə örtülür, bunlar $[3; 5]$ seqmentində üst-üstə düşür:

Cavab $max (ma s [2] [2], ma s [3] [2]) = max (8, 8) = 8$ \max(mas[2][2], mas[3][2]) = \max(8, 8) = 8-dir. $8$ elementi hər iki seqmentə aiddir, lakin bu maksimumun dəyərinə təsir etmir.

Misaldakı bütün sorğular cədvəldə sadalanmışdır:

sorğu	$k$	seqmentlər	maksimumlar	cavab
$110$	$3$	$[1; 8]$ , $[3; 10]$	$10, 10$	$10$
$510$	$2$	$[5; 8]$ , $[7; 10]$	$10, 10$	$10$
$15$	$2$	$[1; 4]$ , $[2; 5]$	$8, 8$	$8$
$26$	$2$	$[2; 5]$ , $[3; 6]$	$8, 8$	$8$
$23$	$1$	$[2; 3]$ , $[2; 3]$	$2, 2$	$2$
$77$	$0$	$[7; 7]$ , $[7; 7]$	$10, 10$	$10$
$78$	$1$	$[7; 8]$ , $[7; 8]$	$10, 10$	$10$
$59$	$2$	$[5; 8]$ , $[6; 9]$	$10, 10$	$10$

$1$ və $2$ uzunluqlu seqmentlər üçün ( $23$ , $77$ və $78$ sorğuları), hər iki örtücü seqment sorğu seqmentinin özü ilə üst-üstə düşür.

Alqoritmin tətbiqi — maksimumun indeksi

$a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) giriş ardıcıllığı $a$ massivində $1$ indeksindən başlayaraq saxlanılır. Bu variantda $ma s [i] [j]$ mas[i][j] xanası $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmentindəki maksimum elementin indeksini saxlayır, maksimumun özü isə $a [ma s [i] [j]]$ a[mas[i][j]]-ə bərabərdir. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, ikinci ölçü üçün $L O GM A X = 17$ LOGMAX = 17 kifayətdir.

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

Build_RMQ_Array funksiyası indekslərin sparse table-ını qurur.

void Build_RMQ_Array()
{

$j = 0$ j = 0 üçün seqment bir elementdən ibarətdir, ona görə $ma s [i] [0] = i$ mas[i][0] = i.

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

$j > 0$ j > 0 üçün, $a$ massivinin $ma s [i] [j - 1]$ mas[i][j - 1] və $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] indeksli elementlərini — seqmentin iki yarısındakı maksimumları — müqayisə edin və böyüyünün indeksini saxlayın.

  for (int j = 1; (1 << j) <= n; j++)
    for (int 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];
}

RangeMaxQuery funksiyası $[i; j]$ seqmentindəki maksimum elementin indeksini qaytarır.

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Əgər $i > j$ i > j olarsa, sərhədlər dəyişdirilir.

  if (i > j) temp = i, i = j, j = temp;

Sonra, dövrdə $2^{k} \leq j - i + 1$ 2^k \le j - i + 1 şərtini ödəyən ən böyük $k$ -nı tapın.

  while ((1 << (k + 1)) <= j - i + 1) k++;

$ma s [i] [k]$ mas[i][k] və $ma s [j - 2^{k} + 1] [k]$ mas[j - 2^k + 1][k] indeksli elementləri müqayisə edin və böyüyünün indeksini qaytarın.

  return (a[mas[i][k]] >= a[mas[j - (1 << k) + 1][k]]) ?
         mas[i][k] : mas[j - (1 << k) + 1][k];
}

Proqramın əsas hissəsi. Massivin ölçüsü $n$ -i və elementlərini $1$ indeksindən başlayaraq oxuyun.

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

$a$ massivindən $ma s$ sparse table-ını qurun.

Build_RMQ_Array();

Sorğuların sayı $q$ -nu oxuyun.

scanf("%d", &q);

Hər sorğu üçün RangeMaxQuery funksiyası $[u; v]$ seqmentindəki maksimum elementin $in d e x$ indeksini qaytarır, biz isə $a [in d e x]$ elementinin özünü çap edirik.

for (i = 0; i < q; i++)
{
  scanf("%d %d", &u, &v);
  int index = RangeMaxQuery(u, v);
  printf("%d\n", a[index]);
}

Alqoritmin tətbiqi — maksimum

$a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) giriş ardıcıllığı $a$ massivində $1$ indeksindən başlayaraq saxlanılır. Bu variantda $ma s [i] [j]$ mas[i][j] xanası $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmentindəki maksimumun özünü saxlayır. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, ikinci ölçü üçün $L O GM A X = 17$ LOGMAX = 17 kifayətdir.

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

Build_RMQ_Array funksiyası $b$ massivindən sparse table-ı qurur:

ma s [i] [j] = max (b [i], b [i + 1], \dots, b [i + 2^{j} - 1])

mas[i][j] = \max(b[i], b[i + 1], \ldots, b[i + 2^j - 1])

void Build_RMQ_Array(int *b)
{

$j = 0$ j = 0 üçün sparse table orijinal massivin elementlərini ehtiva edir: $ma s [i] [0] = b [i]$ mas[i][0] = b[i].

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

$j > 0$ j > 0 üçün $ma s [i] [j]$ mas[i][j] dəyəri seqmentin iki yarısındakı maksimumların böyüyünə bərabərdir.

  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

RangeMaxQuery funksiyası $[i; j]$ seqmentindəki maksimumu qaytarır.

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Əgər $i > j$ i > j olarsa, sərhədlər dəyişdirilir.

  if (i > j) temp = i, i = j, j = temp;

Dövrdə $2^{k} \leq j - i + 1$ 2^k \le j - i + 1 şərtini ödəyən ən böyük $k$ -nı tapın. Bu üsulla $k$ -nın hesablanması loqarifm funksiyasını tələb etmir və üzən vergül xətalarından asılı deyil.

  while ((1 << (k + 1)) <= j - i + 1) k++;

Cavab $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] və $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j] seqmentlərindəki maksimumların böyüyüdür.

  return max(mas[i][k],mas[j - (1<<k) + 1][k]);
}

Proqramın əsas hissəsi. Massivin ölçüsü $n$ -i və elementlərini $1$ indeksindən başlayaraq oxuyun.

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

$a$ massivindən $ma s$ sparse table-ını qurun.

Build_RMQ_Array(a);

Sorğuların sayı $q$ -nu oxuyun. Hər sorğu üçün $[u; v]$ seqmentindəki maksimumu çap edin.

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