题号：NC15814
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
There is a new leisure ground at the gate of HUST. The president of HUST wants to plant a group of trees on the ground and he wants the trees to be planted exactly like a square matrix. And then the gardens start their work. In the next N days, the gardens can water a tree in coordinate: (x, y) and it makes the height of the tree grows H. Sometimes, the president wants to know how magnificent his trees are. The president will give the gardens two coordinates: (x1, y1), (x2, y2). The gardens should report the sum of the heights of the trees in the sub matrix represents by the two coordinates. There will be A days that the gardens will water a tree. And there will be Q days that the president will ask how magnificent his trees are. Apparently, N=A +Q. Furthermore, all the trees’ heights are 0 in the very beginning.
All the absolute values of the inputs and the results are all nonnegative and won't exceed 231-1.
输入描述:
The first line consists of two integers N and W
. N represents the number of days and W represents the size of the matrix. Followed by N lines in two forms:
1 x y H
2 x1 y1 x2 y2
The first one represents the gardeners will water the tree in coordinate (x, y) and it will grow H
.
The second one represents that you need to output the sum of the heights of the trees in the sub matrix represents by the two coordinates.
输出描述:
Your output should consist of Q lines. Each line contains an integer, the result of a query.