Masala G
EKUB so'rovlar
Otabek yaqinda natural sonlar ketma-ketligini o'rganishni boshladi. U quyidagi shartni qondiradigan qism ketma-ketlikni qiziqarli deb hisoblaydi: qism ketma-ketlikdagi barcha elementlarining eng katta umumiy bo'luvchisi 1 dan katta bo'lishi kerak.
Kecha Otabek o'zining garajida N ta natural sonlardan iborat ketma-ketlikni topdi. U juda zerikkanligi sababli, o'zi uchun oddiy savollarni bera boshladi. Har bir savol ikki turdan biriga tegishli:
- X-pozitsiyadagi elementni V qiymatiga o'zgartirish.
- Ketma-ketlikning [L, R] intervalida joylashgan qiziqarli qism ketma-ketliklar sonini aniqlash.
Birinchi qatorda N va Q musbat butun sonlari – ketma-ketlikdagi elementlar soni va so'rovlar soni beriladi. Keyingi qatorda N ta natural son \(A_i\) ketma-ketlikning elementlari sifatida keltirilgan. Keyingi Q qatorda har biri quyidagi shakldagi so'rovlar berilgan:
- Agar so'rov turi 1 bo'lsa, X va V sonlari beriladi, bu holda X -pozitsiyadagi elementning qiymati V ga o'zgartiriladi.
- Agar so'rov turi 2 bo'lsa, L va R sonlari beriladi, bu holda ketma-ketlikning L dan R gacha bo'lgan qiziqarli qism ketma-ketliklar sonini topish kerak.
\(1 \le N, Q \le 10^5\)
\(1 \le X \le N\)
\(1 \le A_i, V_i \le 10^9\)
Har bir 2-turdagi so'rov uchun, ketma-ketlikning qiziqarli bo'laklar sonini alohida qatorda chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 1 8 4 3 9 1 2 2 5 |
4 |
| 2 |
5 3 2 3 6 4 1 2 1 4 1 3 1 2 3 5 |
6 1 |
| 3 |
4 3 2 2 2 2 2 1 4 1 2 3 2 1 4 |
10 5 |
Telegram kanalimizga obuna bo'ling