Masala #33X3AU6PZL
Qat'iy o'suvchi oraliqlar
Uzunligi \(N\) ga teng bo'lgan\(A\) massivi berilgan. \([L, R]\) oraliqqa yoqimtoy oraliq deyiladi, agarda shu oraliqdan tashkil qilgan massiv qat'iy o'suvchi hisoblansa. Boshqa so'zlar bilan aytganda \(A_l < A_{l+1} < ... < A_r\) sharti bajarilishi lozim.
Bundan tashqari \(Q\) ta so'rov mavjud, har bir so'rov uchun \(x\) va \(y\) sonlari kiritiladi. Bundan so'ng massivdagi \(x\)-element \(y\) soniga o'zgaritirladi. Ya'ni \(A_x \leftarrow y\) o'rnatiladi.
\(N\) va \(Q\) kiritiladi \((1 \le N, Q \le 2 * 10^5)\).
Keyingi qatorda N ta butun son - A massiv elementlari kiritiladi \((1 \le A_i \le 10^9)\).
Keyingi Q ta qatorning har birida ikkitadan butun son x va y kiritiladi.
- Subtask #1: \(N, Q \le 80\) (10 ball)
- Subtask #2: \(N, Q \le 500\) (20 ball)
- Subtask #3: \(N, Q \le 5000\) (30 ball)
- Subtask #4: Qo'shimcha cheklovlarsiz (40 ball)
Keyingi \(Q\) ta qatorda har bir so'rovdan so'ng massivdagi qat'iy o'suvchi oraliqlar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 100 10 2 2 3 1 2 1000 |
3 4 |
| 2 |
8 13 10 14 4 20 6 9 16 5 2 3 2 10 1 5 3 15 2 5 |
13 13 15 15 13 |
1-test 1-subtaskning 1-testiga to'g'ri keladi.
2-test 1-subtaskning 2-testiga to'g'ri keladi.
4-subtaskning 1-test: \(A_i = i\), \(Q = 1\), \(x_1 = 1\),\(y_1 = 1\)
Telegram kanalimizga obuna bo'ling