C. Нэгээр нэмэгдүүлэгч функц

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

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

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

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

Поликарпус програм бичих талаар сонирхдог нэгэн. Тэр найзынхаа бичсэн програмын кодыг судалж байгаад $rangeIncrement(l, r)$ гэх функцыг олж үзэв. Энэ функц нь $a$ массивийн $[l, r]$ хооронд орших дугаартай элемент бүр дээр $1$-г нэмдэг. Өөрөөр хэлбэл энэ функц дараах үйлдлийг хийдэг:

function rangeIncrement(l, r)  
    for i := l .. r do  
        a[i] = a[i] + 1

Поликарпус функц хэд хэд дуудагдсаны дараах $a$ массивын утгыг мэдэж байгаа. Тэр $a$ массивын энэ утгыг гаргаж авахын тулд функцийг хамгийн багадаа хэдэн удаа дуудах шаардлагатайг мэдэхийг хүсч байгаа. Бас илүү тодорхой мэдэхийн тулд дуудсан функцуудын $l$, $r$ утгуудыг бас мэдмээр байлаа.

Удалгүй уг функцийг $10^{5}$-ээс бага тооны удаа ажиллуулсан гэдгийг мөн мэдэж авчээ. $rangeIncrement(l, r)$ функцийг анх дуудахаас өмнө массивийн бүх элемент тэгтэй тэнцүү байна.

Поликарпуст хүссэн зүйлээ олж мэдэхэд нь тусална уу.

Оролт

Оролтын эхний мөрөнд массивын элэментүүдийн тоо $n$ байна. $(1 ≤ n ≤ 10^{5})$

Хоёр дахь мөрөнд $rangeIncrement(l, r)$ функцийг хэд хэдэн удаа дуудсаны дараах $a[1], a[2], ..., a[n]$ ($0 ≤ a[i] ≤ 10^{5}$) элементүүдийн утгуудыг зайгаар тусгаарлан оруулна.

Энэ массивын ядаж нэг элемент эерэг тоон утгатай байна. Мөн $rangeIncrement(l, r)$ дуудсан дуудалтын тоо буюу хариу $10^{5}$-аас бага байна.

Гаралт

Эхний мөрөнд оролтонд өгөгдсөн массивыг үүсгэхэд шаардлагатай $rangeIncrement(l, r)$ функцийг дуудсан хамгийн бага тоо $t$-г хэвлэнэ.

Дараа нь бүх дуудалтыг нэг нэг мөрөнд тодорхойлж $t$ мөр хэвлэнэ. Мөр бүрт $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ хоёр бүхэл тоог хэвлэх ба эдгээр нь $i$-р дуудалтанд $rangeIncrement(l, r)$-д дамжуулагдах утгууд юм. Дуудалтуудыг ямар ч дарааллаар хэвлэж болно.

Хэрвээ олон боломж байвал алийг нь ч хэвлэж болно.

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

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

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

Тэмдэглэл

Эхний жишээнд массивыг бүхэлд нь нэг удаа дуудахаас гадна дөрвөн нэмэлт дуудалт байна:

  • $[2,2]$ дуудалт $1$ удаа (массивын хоёр дахь элемент)
  • $[5,5]$ дуудалт $3$ удаа (массивын тав дахь элемент)
Сэтгэгдлүүдийг ачааллаж байна...