D. Пирамидыг хувиргах

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

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

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

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

Вася Петя хоёр сонирхолтой өгөгдөл хадгалах бүтэц болох пирамидыг ашиглаж байна.

Пирамид $n$ мөрөөс бүрдэх ба $i$-р мөрөнд $i$ нүд агуулагдана. Мөр бүр өмнөх мөртэй харьцуулахад хагас нүд зүүн тийшээ шилжсэн байна. Доорх зурганд үзүүлсэнчлэн нүднүүд нэгээс хүртэл бүхэл тоогоор дугаарлагдана.

$n = 5$ байх пирамидын жишээ:

Энэ өгөгдлийн бүтэц хоёр төрлийн үйлдлүүдийг гүйцэтгэж чадна:

  1. Тодорхой нүдний утгыг өөрчлөх. Энэ үйлдэл гурван бүхэл тоон утга $"t i v"$-р тодорхойлогдох ба энд $t = 1$ (үйлдлийн төрөл), $i$ нь утгыг нь солих нүдний дугаар бол $v$ нь нүдэнд бичигдэх утга байна.
  2. Дэд пирамидын утгыг өөрчлөх. Зурагт $5$ нүдэн дээр оройтой дэд пирамидыг тодруулсан байна. Энэ үйлдэл $s + 2$ тоо $"t i v_{1} v_{2} ... v_{s}"$-р тодорхойлогдох ба энд $t = 2$ байх ба $i$ нь пирамидын оройн нүдний дугаар бол $s$ нь дэд пирамидын хэмжээ (дэд пирамидад байгаа нүднүүдийн тоо) харин $v_{j}$ нь дэд пирамидын $j$-р нүдэнд таны бичих ёстой утга юм.

Өөрөөр хэлбэл $k$-р мөрийн $i$-р нүдэн дээр оройтой дэд пирамид $k$-с $n$ хүртэлх мөрүүдийн нүднүүдийг агуулах ба $(k + p)$-р мөр $i$-р нүднээс $(i + p)$ нүд хүртэлх ($0 ≤ p ≤ n - k$) нүднүүдийг агуулна.

Вася Петя хоёрт ижилхэн хоёр пирамид байна. Вася өөрийн пирамидын зарим нүднүүдийг өөрчилсөн ба одоо өөрчлөлтүүдээ Петяруу явуулахыг хүссэн. Үүний тулд Вася түүний найз Петя түүний бүх өөрчлөлтүүдийг давтаж чадах үйлдлүүдийн дарааллыг олохыг хүсч байна. Бүх боломжит дарааллуудын дундаас Вася хамгийн бага нэгийг (хамгийн цөөн тоо агуулсан дараалал) нь сонгоно.

Танд $k$ нүд нь өөрчлөгдсөн $n$ мөртэй пирамид байна. Үр дүнд нь өөрчлөгдсөн $k$ нүд бүр ядаж нэг үйлдлээр өөрчлөгдөх үйлдлүүдийн дарааллыг ол. Боломжит бүх дарааллын дундаас хамгийн цөөхөн тоо агуулсныг нь сонго.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n, k ≤ 10^{5}$) байна.

Дараагийн $k$ мөрөнд өөрчлөгдсөн нүднүүдийн координатууд $r_{i}$ ба $c_{i}$ $(1 ≤ c_{i} ≤ r_{i} ≤ n)$ өгөгдөх ба мөрийн дугаар болон мөр дахь нүдний дугаар байна. Бүх нүднүүд ялгаатай.

Гаралт

Эцсийн дараалалд байх тоонуудын тоог харуулах нэг ширхэг тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 5
3 1
3 3
4 1
4 3
4 4
Гаралт
10
Оролт
7 11
2 2
3 1
4 3
5 1
5 2
5 5
6 4
7 2
7 3
7 4
7 5
Гаралт
26

Тэмдэглэл

Эхний жишээний боломжит шийдлүүдийн нэг нь хоёр үйлдлээс тогтоно:

$2 4 v_{4} v_{7} v_{8}$

$2 6 v_{6} v_{9} v_{10}$

Зурагт өөрчлөгдсөн нүднүүдийг өнгөөр ялгасан байна. Эхний үйлдэлд ашиглагдсан дэд пирамид хөх өнгөөр харин хоёр дахь үйлдэлд ашиглагдсан дэд пирамид шар өнгөөр тэмдэглэгдсэн байна:

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