Masala #TSJZ180QL9

Xotira 256 MB Vaqt 2500 ms
14

Super Struktura

Uzunligi \(n\) ga teng \(a\) massivi berilgan. Sizning vazifangiz jami \(q\) ta 4 xil turdagi so'rovlarga javob berish.

  • \(1 \ x \ y \ z\) so'rovi kiritilganda, har bir \(1 \leq i \leq n\) soni uchun, agar \(x \leq a_i \leq y\) sharti bajarisa, \(a_i \leftarrow z\) amalini bajaring. (\(\leftarrow\) amali o'zlashtirishni anglatadi).
  • \(2 \ l \ r \ c\) so'rovi kiritilganda, har bir \(l \leq i \leq r\) uchun \(a_i \leftarrow c\) amalini bajaring.
  • \(3 \ p\) so'rovi kiritilganda, \(a_p\) ni ekranga chiqaring.
  • \(4 \ p\) so'rovi kiritilganda, \(1 \leq i \leq n\) va \(a_i > a_p\) shartini qanoatlantiruvchi \(i\) lar sonini chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(n, q(1 \leq n, q \leq 200000)\) kiritiladi.

Ikkinchi qatorda \( n\) ta butun son - \(a\) massiv elementlari kiritiladi. Bunda \(1 \leq a_i \leq 10^9\).

Keyingi \(q\) ta qatorining har biri navbatdagi so'rovni anglatadi.

So'rovlar shartda ko'rsatilgani kabi kiritiladi. Quyidagi shartlar doim qanoatlangan:

\(1 \leq x \leq y \leq 10^9, \ 1 \leq z \leq 10^9\)

\(1 \leq l \leq r \leq n, \ 1 \leq c \leq 10^9\)

\(1 \leq p \leq n\)


Chiquvchi ma'lumotlar:

3- yoki 4- turdagi so'rovlarning har biri uchun yangi qatorlarda, so'rovlarning natijasini chiqaring.


Misollar
# input.txt output.txt
1
5 8
1 2 3 2 1
4 5
1 1 1 4
4 3
2 1 2 1
4 4
2 2 3 7
4 1
3 4
3
2
2
4
2