$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS) - Course 3

Modul 1: 2D DP

Eng uzun umumiy quyi-ketma-ketlik (LCS)
Eng uzun o‘suvchi qism ketma-ketlik
$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)
Ryukzak masalasi
Lazy DP

Modul 2: DSU

DSU - Kesishmaydigan to‘plamlar tizimi

Modul 3: MST

Minimal va maksimal qamrovchi daraxtlar
Kruskal algoritmi
Prima algoritmi
Boruvka algoritmi

Modul 4: Kombinatorika

Yulduzlar va ustunlar
Qo‘shish-ayirish prinsipi

Modul 5: Geometriya

Finding the area of a simple polygon

Modul 6: Uzun sonli arifmetika

Uzun arifmetika

Modul 7: Minimum saqlash uchun strukturalar

Minimumli stek
Minimumli navbat
Minimumli deque

Modul 8: Heap [BONUS]

Heap

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Course 3/Modul 1: 2D DP/$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)

$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)

Eng uzun o'suvchi qism ketma-ketlik (LIS) $O(N \log N)$ vaqt ichida

Avval biz dinamik dasturlashdan foydalanib $O(N^2)$ da ishlaydigan LIS masalasining yechimini muhokama qilgan edik. Biz $dp(i)$ = $i$ da tugaydigan eng uzun o‘suvchi ostketma-ketlik uzunligi (bu yerda $a_i$ ketma-ketlikka kiritilgan) formulasiga keldik.

Up next

Ryukzak masalasi

Ryukzak masalasi

dp[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(dp[j] + 1\right)\right)

Ikkilik qidiruvdan foydalanilgan optimallashtirilgan yechim $O(N \log N)$

$O(N^2)$ dan yaxshiroq natijaga erishish uchun, biz $dp$ uchun boshqa holatni tanlashimiz kerak. $dp(l)$ = uzunligi $l$ bo‘lgan qandaydir o‘suvchi ketma-ketlik tugaydigan eng kichik element bo‘lsin. Dastlab $dp$ massivi quyidagicha ko‘rinadi:

dp[l] = \begin{cases} -\infty &\text{$l = 0$ uchun} \\ \infty &\text{$1 \leq l \leq N$ uchun} \end{cases}

So‘ng biz massiv elementlarini birma-bir qayta ishlaymiz va $dp$ ni yangilaymiz. $a_i$ ni qayta ishlashda, har bir $l$ uchun $a_i$ dan foydalanib $l - 1$ uzunlikdagi ketma-ketlikni kengaytirish mumkinmi-yo‘qligini tekshirishimiz kerak. Formal tarzda, har bir $l$ uchun tekshiramiz: agar $dp[l - 1] < a_i$ bo‘lsa va bu rost bo‘ladigan eng kichik $a_i$ ni tanlaymiz hamda $dp[l]$ ni shu qiymatga tenglaymiz. Nega eng kichik shunday $a_i$ ni tanlash optimal ekanini oson ko‘rish mumkin.

Misol

4 ni qayta ishlash: 4 soni birinchi element, shuning uchun u 1 uzunlikdagi ostketma-ketlik tugaydigan eng kichik sondir.
1 ni qayta ishlash: 1 soni DP massivida 4 ni almashtirishi mumkin, chunki 1 kichikroq va u ham 1 uzunlikdagi ostketma-ketlikni tugatadi.
3 ni qayta ishlash: 3 soni 1 dan katta, shuning uchun u ostketma-ketlik uzunligini 2 ga oshiradi. Endi u 2 uzunlikdagi ostketma-ketlikni tugatadigan eng kichik sondir.
2 ni qayta ishlash: 2 soni 3 dan kichik va 1 dan katta, shuning uchun u DP massivida 2 uzunlikdagi ostketma-ketlikning oxirgi elementi sifatida 3 ni almashtiradi.
5 ni qayta ishlash: 5 soni o‘suvchi ketma-ketlikni kengaytiradi; endi u 3 uzunlikdagi ostketma-ketlikni tugatadigan eng kichik sondir.

Ushbu qadamlardan so‘ng $dp$ massivi eng uzun o‘suvchi ostketma-ketlik uzunligi 3 ekanini ko‘rsatadi, bu $\infty$ dan kichik qiymatga ega bo‘lgan eng katta indeksdir.

Sodda (naiv) realizatsiya

Kuzatishlar

E’tibor bering, $dp$ doimo saralangan bo‘ladi, chunki barcha $i = 1 \dots n$ uchun $dp[l-1] < dp[l]$ .
$a_i$ ni qayta ishlashda biz $dp$ da ko‘pi bilan bitta elementni yangilaymiz, chunki faqat bitta $dp[l]$ bo‘lishi mumkin, u uchun $dp[l-1] < a[i] < dp[l]$ bajariladi.

Ushbu kuzatishlarga asoslanib, biz bunday $dp[l]$ ni ikkilik qidiruv yordamida topishimiz mumkin. Biz $dp$ dagi $a_i$ dan qat’iy katta bo‘lgan birinchi elementni topmoqchimiz. Bu $O(\log N)$ dan ko‘p vaqt olmaydi, shunday qilib, umumiy murakkablik $O(N \log N)$ bo‘ladi.

Optimallashtirilgan realizatsiya

[BONUS] Ma’lumotlar tuzilmalaridan foydalanilgan optimallashtirilgan yechim $O(N \log N)$

Keling, bu masalani yechish uchun ishlatgan birinchi $dp$ holatiga qaytaylik.

dp[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(dp[j] + 1\right)\right)

Va endi $t[]$ degan yangi massivni aniqlaymiz, shundayki $t[a[i]] = dp[i]$ .

Endi $dp[i]$ ni hisoblash uchun, bizga $t[]$ massivining prefiksida maksimal qiymatni topish kerak:

dp[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)

Buni Kesma daraxtlari/Fenvik daraxtlari yordamida oson bajarish mumkin.

Cheklovlar

Agar kirish sonlari $a[i]$ katta bo‘lsa, unda biz sonlarni siqish yoki dinamik kesma daraxtidan foydalanish kabi ayrim usullardan foydalanishimizga to‘g‘ri keladi.
Buni ikkilik qidiruvli yechimga qaraganda amalga oshirish ko‘proq vaqt oladi va xotira sarfi yomonroq (daraxtlar uchun kerak bo‘ladi).

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> dp(n+1, INF);
    dp[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int l = 1; l <= n; l++) {
            if (dp[l - 1] < a[i] && a[i] < dp[l])
                dp[l] = a[i];
        }
    }

    int ans = 1;
    for (int l = 1; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n + 1, INF);
    dp[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(dp.begin(), dp.end(), a[i]) - d.begin();
        if (dp[l - 1] < a[i] && a[i] < dp[l])
            dp[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (dp[l] < INF)
            ans = l;
    }
    return ans;
}