G. Зар сонгох

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Саяхан нэгэн олон нийтийн сүлжээг хөгжүүлэгч хэрэглэгч нарт заруудыг сонгон харагдуулах шинэ алгоритмыг санал болгожээ.

Зар тавигч худалдан авч болох нийтдээ $n$ ширхэг хоосон орон зай байх ажээ. Түүнчлэн нэгэн зэрэг хэд хэдэн дараалсан хоосон орон зайнуудын сегментийг худалдан авах боломжтой байв. Та аль болох олон хоосон орон зайг эзэмших тусам таны зар хэрэглэгчдэд хүрэх магадлал ихсэх юм.

Хугацааны хором бүрд хэрэглэгчдэд харагдах заруудыг сонгохын тулд бид нэгэн нууц алгоритмын дагуу хэсэг хоосон орон зайнуудын сегментийг сонгох хэрэгтэй ажээ. Дараа нь хэсэг зар тавигчдыг сонгох ба уг сонгогдсон сегментийг бүрдүүлж буй хоосон орон зайнуудын дор хаяж $p$%-ыг эзэмшиж буй зар тавигчдын зарууд нь заавал хэрэглэгчдэд хүрэх ёстой байв.

Нөгөө талаас хэрэглэгчид зар харах болон үзэх дургүй бөгөөд ийм учраас хэрэглэгчдэд нэг удаа зар хүргэхдээ -аас ихгүй зарыг хүргэж байхаар шийджээ. Та хоосон орон зайнуудын сегментийг худалдаалах системийг хөгжүүлэхээр болсон бөгөөд дээр дүрсэлсэн дүрмийн дагуу хэрэглэгчдэд хүргэх зарыг сонгох ёстой болжээ.

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $p$ ($1 ≤ n, m ≤ 150 000, 20 ≤ p ≤ 100$) өгөгдөх ба эдгээр нь хоосон орон зайнуудын тоо, таны системд өгөгдөх асуултуудын тоо болон ямар зар нь хэрэглэгчдэд баттай хүрэхийг илэрхийлэх босго утгыг тус тус илэрхийлнэ.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $a_{i}$ ($1 ≤ a_{i} ≤ 150 000)$-ууд өгөгдөх ба эдгээрийн $i$-дахь тоо нь $i$-р хоосон орон зайг одоогоор эзэмшиж буй зар тавигчийн дугаарыг илэрхийлнэ.

Дараагийн $m$ мөрөнд асуултуудыг дүрсэлнэ. Асуулт болгон нь дараах 2 хэлбэрийн аль нэг хэлбэрээр өгөгдөнө:

  • 1 l r id ($1 ≤ l ≤ r ≤ n, 1 ≤ id ≤ 150 000$) -- $id$ гэсэн дугаартай зар тавигч нь $l$-ээс $r$ хүртэлх (эдгээр тоонууд нь өөрсдөө энэ завсартаа орно) завсар дахь бүх хоосон орон зайнуудыг худалдан авсан;
  • 2 l r ($1 ≤ l ≤ r$) -- та $[l, r]$ гэсэн сегментийн хувьд зар тавигчдыг сонгох хэрэгтэй байна.

Гаралт

2-р төрлийн асуулт бүрийн хувьд хариултууд нь тусдаа салангид мөрүүдэд хэвлэгдсэн байна. Хариултын эхэнд байх бүхэл тоо нь хэрэглэгчдэд хүрэх заруудын тоо байх ёстой бөгөөд $cnt$-ын дараах бүхэл тоонууд нь зар тавигчдын дугаарууд байх юм.

Ямар нэгэн зар тавигчийг нэгээс олон удаа хэвлэсэн байж болох боловч $l$-ээс $r$ хүртэлх сегментийн хоосон орон зайнуудын дор хаяж -ыг эзэмшиж буй зар тавигчид нь заавал таны хариултад байх ёстойг анхаарна уу.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5 9 33
1 2 1 3 3
2 1 5
2 1 5
2 1 3
2 3 3
1 2 4 5
2 1 5
2 3 5
1 4 5 1
2 1 5
Гаралт
3 1 2 3
2 1 3
2 2 1
3 1 1000 1000
1 5
2 5 3
2 1 5

Тэмдэглэл

Жишээнүүд нь та зар тавигчдыг сонгохдоо маш дураараа сонгох боломжтой болохыг харуулсан байна.

Сэтгэгдлүүдийг ачааллаж байна...