USUBQSUB - Update Sub-Matrix & Query Sub-Matrix

题意翻译

给定一个$N*N$且每个单元初始值都为0的矩阵,你将进行$M$次如下两种之一的操作: 操作一 1 $x_1$ $y_1$ $x_2$ $y_2$ 询问以 $x_1$ $y_1$ 单元为左上角, $x_2$ $y_2$ 单元为右下角的子矩阵内所有单元值的总和。 操作二 2 $x_1$ $y_1$ $x_2$ $y_2$ $k$ 使以 $x_1$ $y_1$ 单元为左上角, $x_2$ $y_2$ 单元为右下角的子矩阵内所有单元的值加上$k$。 对于每个操作一,输出它的结果。

题目描述

Updating and querying 1 dimensional arrays is a popular question. How about updating and quering sub-matrices of a matrix? A sub-matrix will be depicted as (a, b), (c, d). This implies that it will include all the cells (x, y) such that a<=x<=c and b<=y<=d. The matrix is indexed from \[1..N\]\[1..N\], where N is the size. You are given a matrix of size NxN, with each element initially set to 0. There are M queries and each query can be of one of the two types: 1 x1 y1 x2 y2: This query asks you to return the sum of all the elements in the sub-matrix (x1, y1), (x2, y2). 2 x1 y1 x2 y2 K: This query asks you to add K to each element in the sub-matrix (x1, y1), (x2, y2).

输入输出格式

输入格式


The first line of input contains N, M. The next M lines contain queries in the same forms as stated above. You may assume that x1<=x2 and y1<=y2 for all queries. Also N<=1000 and M<=10 $ ^{5} $ . K<=10 $ ^{9} $

输出格式


The answer to all the queries wherein you need to return the sum of elements in the sub-matrix, i.e., all the queries of type 1.

输入输出样例

暂无测试点