C. Дзи өнгөнүүдэд дуртай

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

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

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

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

Дзи өнгөнүүдэд дуртай ба тэр гайхалтай зурдаг.

Нэгэн өнгөлөг өдөр Дзи $n$ нэгжтэй (зүүнээс баруун тийш $1$-с $n$ хүртэл дугаарлагдсан) өнгийн тууз авав. Энэ нь хангалттай өнгөлөг хэдий ч бид одоо нэгж тус бүрийн өнгөний нэвтрэл эхлээд $0$ гэж үзэж байна.

Дзи зурах дуртайг бид мэднэ. Тэр $x$ өнгөтэй багс аваад түүнийгээ ашиглан туузан дээр шугам зурсан. Энэ тохиолдолд зарим зэрэгцэн оршдог нэгжүүд будагдсан байна. $i$ нэгжийн өнгө одоо $y$ болсон гэж бодъё. Энэ багсаар будагдсан нэгжийн өнгө $x$ болсон ба өнгөний нэвтрэл $|x - y|$ нэгжээр нэмэгдсэн.

Дзи $m$ үйлдлүүд гүйцэтгэхийг хүссэн ба үйлдэл бүр нь дараах хоёрын нэг байна:

  1. $l$ болон $r$ (оруулаад) хоорондох тоонуудын бүх нэгжийг $x$ өнгөөр будна.
  2. $l$ болон $r$ (хоёуланг нь оруулаад) хоорондох нэгжүүдийн өнгөний нэвтрэлийн нийлбэрийг асууна.

Дзид тусалж чадах уу?

Оролт

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

Дараагийн $m$ мөр бүр нь $type (1 ≤ type ≤ 2)$ бүхэл тоогоор эхлэнэ, энэ үйлдлийн төрлийг илэрхийлнэ.

Хэрвээ $type = 1$, бол энэ мөрөнд $3$ бүхэл тоо байна $l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 10^{8})$, үйлдэл $1$-г тодорхойлно.

Хэрвээ $type = 2$, бол энэ мөрөнд $2$ бүхэл тоо байна $l, r (1 ≤ l ≤ r ≤ n)$, үйлдэл $2$-г тодорхойлно.

Гаралт

Үйлдэл $2$ бүрийн хариуг агуулсан мөр хэвлэнэ. Энэ нь өнгөний нэвтрэлийн нийлбэр.

Орчуулсан: Даариймаа

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

Оролт
3 3
1 1 2 4
1 2 3 5
2 1 3
Гаралт
8
Оролт
3 4
1 1 3 4
2 1 1
2 2 2
2 3 3
Гаралт
3
2
1
Оролт
10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10
Гаралт
129

Тэмдэглэл

Эхний жишээнд нэгж бүрийн өнгө нь эхлээд $[1, 2, 3]$, ба өнгөний нэвтрэл нь $[0, 0, 0]$.

Эхний үйлдлийн дараа өнгөнүүд $[4, 4, 3]$ болно, өнгөний нэвтрэл $[3, 2, 0]$ болно.

Хоёр дахь үйлдлийн дараа өнгөнүүд $[4, 5, 5]$ болно, өнгөний нэвтрэл $[3, 3, 2]$ болно.

Ингээд зөвхөн $2$ төрлийн асуултын асуултын хариулт $8$ байна.

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