Masala #GWXVNFZDPF
Darvozalarni qo'riqlash
Yaqindagina juda katta “DataToMoney” banki barpo etildi. Bu bank shunchalar kattaki, unda \(N\) ta darvozasi mavjud. Hali yangi bo‘lgani uchun hozircha bankning hech qaysi darvozasida qo‘riqchilar joylashtirilmagan.
Bank direktori \(Q\) marta quyidagi ikki xil so‘rovdan birini berishi mumkin.
- Birinchi turdagi so‘rov: \([l…r]\) oraliqdagi barcha darvozalarga lavozimi\(v\) bo‘lgan yangi qo‘riqchini tayinlash. Bunda shu oraliqdagi biron darvozalarni boshqa qo‘riqchi nazorat qilayotgan bo‘lsa, bu qo‘riqchi boshqa bu darvozani nazorat qilmasin.
- Ikkinchi turdagi so‘rov: eng zaif qo‘riqlanayotgan darvozalar sonini aytishingiz kerak bo‘ladi. \(i\)-darvoza \(j\)-darvozadan zaifroq qo‘riqlanadi, agar \(i\)-darvozani nazorat qiluvchi qo‘riqchi lavozimi, \(j\)-darvozani qo‘riqlovchi darvoza qo‘riqchisi lavozimidan kichikroq bo‘lsa, yoki \(j\)-darvoza qo‘riqlanib \(i\)-darvoza umuman qo‘riqlanmasa.
Siz direktorning so‘rovlarini bajaruvchi dastur tuzing. Bunda faqatgina 2-turdagi so‘rov uchun eng zaif qo‘riqlanayotgan darvozalar sonini chiqaring.
2-turdagi so‘rovdan kamida bitta berilishi kafolatlanadi.
Birinchi qatorda ikkita butun son - \(N, Q(1 ≤ N, Q ≤ 2 * 10^5 )\) bankdagi darvozalar va direktorning so‘rovlari soni.
Keyingi \(Q\) ta qatorning har birida so‘rovni turini ifodalovchi \(t ∈ [1,2]\) kiritiladi. Agar \(t=2\)bo‘lsa, demak so‘rov ikkinchi turda. Agar \(t = 1\) bo‘lsa so‘rov birinchi turda, hamda qo‘shimcha tarzda \(l, r, v(1 ≤ l ≤ r ≤ N, 1 ≤ v ≤ 10^9)\)lar kiritiladi.
Har bir 2-turdagi so'rov uchun alohida qatorda eng zaif qo'riqlanayotgan darvozalar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
8 9 2 1 1 4 3 2 1 5 7 6 1 3 4 5 1 8 8 9 2 1 1 8 20 2 |
8 4 2 8 |
Tushuntirish:
So‘rovlardan oldin darvozalarning qo‘riqlanish holati [0,0,0,0,0,0,0,0] bo’lgan. (0 - hech qaysi qo‘riqchi darvozani qo‘riqlamasligini anglatadi).
Hech qaysi darvoza qo‘riqlanmaganligi sababli 1-so‘rov uchun javob 8.
2-so‘rovdan so‘ng darvozalarning qo‘riqlanish holati [3,3,3,3,0,0,0,0] bo‘ladi.
Endi eng zaif qo‘riqlanayotgan darvozlalar [5…8] o‘rindagi darvozalardir. Shuning uchun ham 3-so‘rovga javob 4.
6-so‘rovdan so‘ng darvozalarning qo‘riqlanish holati [3,3,5,5,6,6,6,9] bo‘ladi.
Endi [1…2] o‘rindagi darvozalar eng zaif qo‘riqlangandir. Shuning uchun ham 7-so‘rovga javob 2.
Telegram kanalimizga obuna bo'ling