E. Алимхүү ба хуудас цаас

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

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

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

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

Алимхүүд маш том хуудас цаас байв. Энэ цаас $1 × n$ хэмжээтэй тэгш ѳнцѳгт хэлбэртэй. Таны даалгавар Алимхүүд энэхүү цаасыг нугалахад нь туслах явдал юм. Үнэн хэрэгтээ та бас $q$ хүсэлтийг биелүүлэх шаардлагатай. Хүсэлт бүр дараах хэлбэрүүдийн аль нэг нь байна:

  1. $p_{i}$ цэгээс нугалах. Энэ хүсэлтийн дараа цаасны зүүн талаас $1 × p_{i}$ хэмжээтэйгээр нугалж цаасны баруун хэсэг болох $1 × ([цаасны\ тухайн\ үеийн\ урт] - p_{i})$ хэмжээтэй хэсэг дээр тавина.
  2. Цаасны нэг хэсгийг таславал энэ хэсэгт хэр урт цаас байхыг тооцоолно. Тухайн үед байгаа цаасны зүүн талаас $l_{i}$, $r_{i}$ зайтайгаар таслахад энэ хооронд байх цаасны нийт хэмжээг олох хэрэгтэй.

Эхний жишээний тайлбарыг үзвэл энэ бодлогыг илүү сайн ойлгох болно.

Оролт

Эхний мѳр цаасны урт, хүсэлтийн тоо болох хоёр бүхэл тоог агуулна: $n$, $q$ ($1  ≤ n ≤ 10^{5}; 1 ≤ q ≤ 10^{5}$).

Дараагийн $q$ мѳр бүр доорх хэлбэртэй байна:

  • "$1$ $p_{i}$" $(1 ≤ p_{i} < [цаасны\ тухайн\ үеийн\ урт])$ - нэгдүгээр тѳрлийн хүсэлт.
  • "$2$ $l_{i}$ $r_{i}$" $(0 ≤ l_{i} < r_{i} ≤ [цаасны\ тухайн\ үеийн\ урт])$ - хоёрдугаар тѳрлийн хүсэлт.

Гаралт

Хоёрдугаар тѳрлийн хүсэлт бүрийн хариуг буцаа.

Орчуулсан: Sugardorj

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

Оролт
7 4
1 3
1 2
2 0 1
2 1 2
Гаралт
4
3
Оролт
10 9
2 2 9
1 1
2 0 1
1 8
2 0 8
1 2
2 1 3
1 4
2 2 4
Гаралт
7
2
10
4
5

Тэмдэглэл

Эхний жишээн дэх хүсэлтүүдийн хувьд цаас доорх хэлбэртэй байна:

Эхний нугалалтын дараах урт $4$, хоёрдахь нугалалтын дараах урт $2$ болж байна.

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