D. Тогтвортой номын шүүгээ

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

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

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

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

Алина саяхан сургууль дээрээ тогтвортой өгөгдлийн бүтэц гэж юу болох талаар сурчээ. Тухайлбал тогтвортой өгөгдлийн бүтэц гэдэг нь үргэлж өөрийнхөө өмнөх төлвийн мэдээллийг хадгалж байх бөгөөд өөрчлөлт хийх үед хандах боломжтой байдаг өгөгдлийн бүтэц юм.

Гэртээ харьсныхаа дараа Алина өөрийн тогтвортой өгөгдлийн бүтцийг зохион бүтээхээр шийджээ. Үүнийг зохион бүтээхэд их цаг зарцуулаагүй бөгөөд түүний орны ард нэгэн номын шүүгээ байрлаж байв. Иймд тэрээр уг номын шүүгээг тогтвортой өгөгдлийн бүтэц болгон сонгоход яг тохирно хэмээн үзжээ. Анхандаа номын шүүгээ нь хоосон байх бөгөөд уг шүүгээний аль ч тавцангийн аль ч байрлал дээр ямар ч ном байхгүй байх юм.

Номын шүүгээ нь $n$ ширхэг номын тавцангаас тогтох ба тавцан болгон нь яг $m$ ширхэг ном байрлуулж болох байрлалтай байв. Алина номын тавцангуудыг $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлах бөгөөд тавцангууд дээрх байрлалуудыг $1$-ээс $m$ хүртэлх бүхэл тоонуудаар дугаарлав. Анхандаа номын шүүгээ нь хоосон байх бөгөөд уг шүүгээний аль ч тавцангийн аль ч байрлал дээр ямар ч ном байхгүй байв.

Алина $q$ ширхэг үйлдэл бичсэн ба эдгээр үйлдлүүдийг номын шүүгээнд дарааллын дагуу гүйцэтгэх юм. Үйлдэл болгон нь дараах 4 төрлийн аль нэг нь байна:

  • $1$ $i$ $j$ -- Хэрэв $i$-р тавцангийн $j$-р байрлал дээр ном байхгүй байвал уг байрлал дээр ном байрлуулна.
  • $2$ $i$ $j$ -- Хэрэв $i$-р тавцангийн $j$-р байрлал дээр ном байвал уг байрлал дээрх номыг авч хаяна.
  • $3$ $i$ -- $i$-р тавцангийн дүүргэлтийг тонгоргоно. Энэ нь $i$-р тавцан дээрх номтой бүх байрлал дээрх номуудыг авч хаях ба $i$-р тавцан дээрх номгүй бүх байрлал дээр ном байрлуулна гэсэн үг юм.
  • $4$ $k$ -- $k$-дахь үйлдлээс хойш номын шүүгээнд нэмэгдсэн бүх номуудыг буцаана. Тодруулбал, $k = 0$ гэдэг нь номын шүүгээ нь анхны байрлалдаа очно гэсэн үг бөгөөд иймд номын шүүгээнд байрлах бүх ном нь өөрсдийн байрлалаасаа авч хаягдах юм.

Үйлдэл тус бүрийг гүйцэтгэсний дараа Алина номын шүүгээнд байрлах нийт номын тоог мэдэхийг хүсжээ. Алина сургууль дээрээ 'A' үнэлгээтэй суралцдаг бөгөөд уг утгыг олоход ямар ч асуудалгүй байв. Харин та уг утгыг олж чадах уу?

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $q$ ($1 ≤ n, m ≤ 10^{3}$, $1 ≤ q ≤ 10^{5}$) өгөгдөх ба эдгээр нь харгалзан номын шүүгээний хэмжээ болон нийт хийх үйлдлийн тоог илэрхийлнэ.

Дараагийн $q$ мөрөнд үйлдлүүдийг гүйцэтгэх дарааллаар нь дүрсэлсэн байна. Эдгээрийн $i$-дахь нь бодлогын нөхцөлд дүрсэлсэн 4 төрлийн аль нэг төрлийн үйлдэл буюу $i$-дахь үйлдлийг дүрсэлнэ.

Мөн түүнчлэн тавцангуудын дугаарууд болон байрлалуудын дугаарууд нь алдаагүй үнэн зөв байх бөгөөд 4-р төрлийн үйлдэл болгоны хувьд $k$ тоо нь уг үйлдлийн өмнөх үйлдлийг заана эсвэл $0$-тэй тэнцүү байх юм.

Гаралт

Үйлдэл бүрийн хувьд уг үйлдлийг гүйцэтгэсний дараах номын шүүгээнд байх номын тоог тусдаа салангид мөрүүдэд хэвлэнэ үү. Түүнчлэн хариултууд нь цаг тооллын дарааллаар хэвлэгдсэн байх ёстойг анхаарна уу.

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

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

Оролт
2 3 3
1 1 1
3 2
4 0
Гаралт
1
4
0
Оролт
4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2
Гаралт
2
1
3
3
2
4
Оролт
2 2 2
3 2
2 2 1
Гаралт
2
1

Тэмдэглэл

Уг зурагт 2-дахь жишээг дүрсэлж үзүүлэв.

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