Seyrək cədvəllər (Həll təhlili)

Məsələdə generasiyadan sonra dəyişməyən massivin bir seqmentində minimumun təkrar-təkrar tapılması tələb olunur. Sorğuların sayı $1 0^{7}$ 10^7-ə çatır, ona görə hər bir sorğu $O (1)$ vaxtında emal olunmalıdır. Bunun üçün biz sparse table — RMQ (Range Minimum Query) məsələsi üçün statik məlumat strukturundan istifadə edirik.

Cədvəlin qurulması. Hər bir $i$ mövqeyi və $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n şərtini ödəyən hər bir $j$ üçün $ma s [i] [j]$ mas[i][j] xanasında $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmentinin (uzunluğu $2^{j}$ 2^j) minimum elementinin indeksi saxlanılır. $j = 0$ j = 0 üçün seqment bir elementdən ibarətdir, ona görə $ma s [i] [0] = i$ mas[i][0] = i.

$j > 0$ j > 0 üçün uzunluğu $2^{j}$ 2^j olan seqmenti uzunluğu $2^{j - 1}$ 2^{j-1} olan iki yarıya bölürük: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] və $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. Yarılardakı minimumların indeksləri artıq hesablanıb — bunlar $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]-dir:

Bütün seqmentin minimumu yarıların iki minimumundan kiçik olanına bərabərdir. Buna görə $ma s [i] [j]$ mas[i][j] bu iki indeksdən – $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] – hansı daha kiçik massiv elementini göstərirsə ona bərabər olur. Cədvəl $j$ -nin artma ardıcıllığı ilə doldurulur və $O (n lo g n)$ O(n \log n) xana saxlayır.

Sorğuya cavab vermək. Tutaq ki, $[u; v]$ seqmentində minimumu tapmaq lazımdır. $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor olsun – seqmentin uzunluğunu aşmayan ən böyük ikinin qüvvətinin göstəricisi. $u$ -dan başlayan uzunluğu $2^{k}$ 2^k olan seqment və $v$ -də bitən uzunluğu $2^{k}$ 2^k olan seqment birlikdə $[u; v]$ -ni tamamilə örtür, çünki $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

Bu seqmentlər üst-üstə düşə bilər, lakin bu, minimum üçün heç bir əhəmiyyət daşımır: iki dəfə hesablanan element nəticəni dəyişmir (məsələn, cəmdən fərqli olaraq). Deməli, $[u; v]$ -dəki minimum $a [ma s [u] [k]]$ a[mas[u][k]] və $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]] elementlərindən kiçik olanına bərabərdir, və sorğu $O (1)$ vaxtında emal olunur.

Generasiya olunan sorğuların $u$ və $v$ sərhədləri istənilən ardıcıllıqla gələ bilər, ona görə sorğunu yerinə yetirməzdən əvvəl onları zərurət olduqda yer dəyişdiririk.

Mürəkkəblik. Cədvəlin qurulması $O (n lo g n)$ O(n \log n) vaxt aparır, hər bir sorğu isə $O (1)$ vaxtında işlənir. Ümumi mürəkkəblik $O (n lo g n + m)$ O(n \log n + m)-dir. $m \leq 1 0^{7}$ m \le 10^7 olduğundan, məhz $O (1)$ sorğu vaxtı zaman limitinə sığmağa imkan verir.

Misal

Misala baxaq: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. Generasiya olunmuş massiv məsələnin şərtindəki massivlə üst-üstə düşür. Bunun üçün $ma s$ cədvəli aşağıda göstərilmişdir. Xanalarda minimum elementlərin indeksləri yazılmışdır; tire işarəsi seqmentin massivin hüdudlarından kənara çıxdığını bildirir.

$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$	—	—	—	—	—	—	—

Məsələn, $ma s [3] [2] = 5$ mas[3][2] = 5: $[3; 6]$ seqmentində minimum element $a_{5} = 1565158$ a_5 = 1565158-dir. $ma s [2] [3] = 2$ mas[2][3] = 2 dəyəri $ma s [2] [2] = 2$ mas[2][2] = 2 və $ma s [6] [2] = 8$ mas[6][2] = 8-dən alınır, çünki $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265.

Birinci sorğu: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. Seqmentin uzunluğu $7$ -dir, ona görə $k = 2$ k = 2. $[3; 9]$ seqmenti $[3; 6]$ və $[6; 9]$ seqmentləri ilə örtülür, onlar üçün $ma s [3] [2] = 5$ mas[3][2] = 5 və $ma s [6] [2] = 8$ mas[6][2] = 8-dir. $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158 olduğundan, cavab $an s_{1} = 570265$ ans_1 = 570265-dir.

İkinci sorğunun parametrləri:

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.

$u_{2} > v_{2}$ u_2 > v_2 olduğundan, sərhədlər yer dəyişdirilir, və $[1; 10]$ seqmentindəki minimum hesablanır.

Bütün sorğular cədvəldə göstərilmişdir:

$i$	$u_{i}$ \boldsymbol{u_i}	$v_{i}$ \boldsymbol{v_i}	seqment	$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$

Son sorğunun parametrləri $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3-dür, və onun cavabı $an s_{8} = 1565158$ ans_8 = 1565158-dir. Məhz bu qiymətlər çap olunur. Qeyd edək ki, seqmentin sıralanmış sərhədləri deyil, $u_{8}$ u_8 və $v_{8}$ v_8-in ilkin qiymətləri çap olunur.

Alqoritmin reallaşdırılması

$a$ massivinin elementləri ( $n \leq 1 0^{5}$ n \le 10^5) $1$ -ci indeksdən başlayaraq saxlanılır. $l g 2 [i]$ massivi $i$ ədədinin $2$ əsası üzrə loqarifminin tam hissəsini saxlayır.

#define MAX 100001
#define LOGMAX 17
int a[MAX], lg2[MAX];

Sparse table $ma s$ massivində saxlanılır: $ma s [i] [j]$ mas[i][j] – $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmentinin minimum elementinin indeksidir. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, $j$ -nin qiymətləri $16$ -dan artıq deyil, ona görə ikinci ölçü üçün $L O GM A X = 17$ LOGMAX = 17 kifayətdir.

int mas[MAX][LOGMAX];

check funksiyası $u > v$ u > v olduqda $u$ və $v$ -nin qiymətlərini yerini dəyişir ki, $u \leq v$ u \le v olsun. Parametrlər istinad ilə ötürülür.

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

RMQ_nlogn funksiyası sparse table-ı qurur.

void RMQ_nlogn(void)
{

$2$ -dən $n$ -ə qədər bütün ədədlər üçün $⌊ l o g_{2} i ⌋$ \lfloor log_2 i \rfloor tam loqarifm qiymətlərini hesablayırıq.

  for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;

Əvvəlcə bütün $i$ üçün $ma s [i] [0] = i$ mas[i][0] = i.

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

Sonra, $2^{j} \leq n$ 2^j \le n şərti ödəndikcə hər bir $j$ üçün və $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] seqmenti massivin hüdudlarından kənara çıxmadıqca hər bir $i$ üçün, $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]-dən kiçik elementin indeksini seçirik.

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

q funksiyası $[i; j]$ seqmentindəki minimum elementin indeksini qaytarır. $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor hesablanır və uzunluğu $2^{k}$ 2^k olan iki seqmentin minimumları müqayisə edilir: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] və $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

int q(int i, int j)
{
  int k = lg2[j - i + 1];
  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. $n$ , $m$ , massivin ilk elementi $a_{1}$ a_1 və birinci sorğunun $u$ və $v$ parametrlərini oxuyuruq.

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

Məsələnin şərtindəki düsturdan istifadə edərək $a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n elementlərini generasiya edirik. $23 \cdot a_{i}$ 23 \cdot a_i hasili $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8-dən aşmır və $in t$ tipinə sığır.

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

$ma s$ sparse table-ını qururuq.

RMQ_nlogn();

$m$ sorğunu bir-bir emal edirik.

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

Cari sorğunun sərhədlərini $u 1$ və $v 1$ -ə köçürürük və zərurət olduqda check funksiyası ilə onları sıralayırıq. $u$ və $v$ -nin özləri dəyişdirilmir: növbəti sorğunun parametrləri onlardan hesablanır, və məhz onlar cavabda çap olunur.

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

$[u 1; v 1]$ [u1; v1] seqmentindəki minimum elementi tapırıq.

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

Əgər sorğu sonuncu deyilsə, məsələnin şərtindəki düsturlardan istifadə edərək növbəti sorğunun parametrlərini hesablayırıq.

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

Son sorğunun parametrlərini və onun cavabını çap edirik.

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