E. Инна ба том чихэрлэг матриц

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

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

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

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

Инна чихэрлэг зүйлд үнэхээр дуртай.Тиймээс тэрээр чихэрлэг матриц гэх тоглоомыг Дима болон Сережа-тай тоглохоор шийджээ.Гэхдээ Сережа том хүн тул уг тоглоом нь түүний бага санагджээ.Тиймээс Сережа "Том чихэрлэг матриц" гэх тоглоомын тоглохыг санал болгов.

"Том чихэрлэг матриц" нь $n × m$ матрицан талбар дээр тоглоно.Матрицын мөрүүдийг $1$-ээс $n$ хүртэл дугаарлах ба багануудыг $1$-ээс $m$ хүртэл дугаарлана.$i$-дахь мөр болон $j$-дэх баганын нүдийг $(i, j)$ гэж тэмдэглэе.Матрицийн нүд бүр нь олон тооны чихэртэй байж болох бөгөөд анхандаа бүх нүднүүд нь хоосон байх юм.Тоглоом нийтдээ $w$ нүүдэл хийх ба нүүдэл бүр нь дараах 2 төрлийн нэгээр нүүх юм:

  1. Сережа $x_{1}, y_{1}, x_{2}, y_{2}, v$ $(x_{1} ≤ x_{2}, y_{1} ≤ y_{2})$ гэсэн 5-н бүхэл тоо сонгох ба $v$ ширхэг чихрийг матрицийн $(i, j)$ $(x_{1} ≤ i ≤ x_{2}; y_{1} ≤ j ≤ y_{2})$ байх нүд бүр дээр нэмнэ.
  2. Сережа $x_{1}, y_{1}, x_{2}, y_{2}$ $(x_{1} ≤ x_{2}, y_{1} ≤ y_{2})$ гэсэн 4-н бүхэл тоо сонгоно.Дараа нь тэрээр Дима-аас $(i, j)$ $(x_{1} ≤ i ≤ x_{2}; y_{1} ≤ j ≤ y_{2})$ нүднүүдэд байх нийт чихрийн тоог тооцоолохыг хүсэх ба Инна-аас дараах шалгуурыг хангах $(p, q)$ матрицийн нүднүүдэд байх нийт чихрийн тоог тооцоолохыг хүснэ.Үүнд:($p < x_{1}$ эсвэл $p > x_{2}$) болон ($q < y_{1}$ эсвэл $q > y_{2}$) байна.Эцэст нь Сережа Дима-ийн тооцоолсон тоо болон Инна-ийн тооцоолсон тоонуудын зөрүү буюу (D - I)-г бичихийг хүсэх юм.

Харамсалтай нь Сережа-ийн матриц үнэхээр том юм.Тиймээс Инна болон Дима тооцоолж чадахгүй байгаа аж.Тэдэнд тусална уу!

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $w$ $(3 ≤ n, m ≤ 4*10^{6}; 1 ≤ w ≤ 10^{5})$ өгөгдөнө.

Дараагийн $w$ мөрөнд тоглоомд хийгдэх үйлдлүүдийг тодорхойлно.

  • Эхний төрлийн нүүдлийг тодорхойлох мөрөнд 6-н бүхэл тоо өгөгдөнө: $0$, $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ болон $v$ $(1 ≤ x_{1} ≤ x_{2} ≤ n; 1 ≤ y_{1} ≤ y_{2} ≤ m; 1 ≤ v ≤ 10^{9})$.
  • 2-дахь төрлийн нүүдлийг тодорхойлох мөрөнд 5-н бүхэл тоо өгөгдөнө: $1$, $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ $(2 ≤ x_{1} ≤ x_{2} ≤ n - 1; 2 ≤ y_{1} ≤ y_{2} ≤ m - 1)$.

2-дахь төрлийн нүүдэл дор хаяж 1 удаа өгөгдөнө.Мөн нэг үйлдэл хийгдэх үед $10^{9}$-өөс илүү тооны чихэр нэмэгдэхгүй.

Анхааралтай байна уу,шалгуур маш өндөр учраас оновчтой өгөгдлийн бүтцийг хэрэглэнэ үү.Мөн макс-тестүүд шалгагч тестүүдэд байна.

Гаралт

2-дахь төрлийн нүүдэл бүрийн хувьд дан мөрөнд Дима болон Инна-ийн тоонуудын зөрүү болох ганц бүхэл тоог хэвлэнэ.

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

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

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

Тэмдэглэл

Жишээг авч үзье. Эхний нүүдлийн дараа матриц нь дараах байдалтай байна:

22200  
22200   
00000  
00000

2-дахь нүүдлийн дараа:

22200  
25500  
03300   
00000

3-дахь нүүдлийн дараа:

22201  
25501  
03301  
00001

4-дэх нүүдлийн хувьд, Дима-ийн нийлбэр нь 5 + 0 + 3 + 0 = 8 байх ба Инна-ийн нийлбэр нь 4 + 1 + 0 + 1 = 6 байна.Тиймээс асуултын хариулт нь 8 - 6 = 2 байна.5-дахь нүүдлийн хувьд Димагийн нийлбэр нь 0 байх ба Инна-ийн нийлбэр нь 18 + 2 + 0 + 1 = 21 байна.Иймээс асуултын хариулт нь 0 - 21 = -21 байна.

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