RoboContest

Xotira 64 MB Vaqt 2500 ms

14

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir 2-turdagi so'rov uchun alohida qatorda eng zaif qo'riqlanayotgan darvozalar sonini chop eting.

Misollar

#	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

Izoh:

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.

RoboContest

Masala #GWXVNFZDPF

Darvozalarni qo'riqlash