bzoj#P1176. [Balkan2007] Mokia

[Balkan2007] Mokia

题目描述

维护一个 w×ww\times w 的矩阵,初始值均为 ss。每次操作可以增加某格子的权值,或询问某子矩阵的总权值。修改操作数 mm,询问数 qq

输入格式

第一行两个整数,ssww,其中 ss 为矩阵初始值,ww 为矩阵大小。

接下来每行为一下三种输入之一:

  • 1 x y a:你需要把 (x,y)(x,y)(第 xx 行第 yy 列)的格子权值增加 aa

  • 2 x y x y:你需要求出以左下角为 (x1,y1)(x_1, y_1),右上角为 (x2,y2)(x_2, y_2) 的矩阵内所有格子;

  • 3:表示输入结束。

输出格式

对于每个输入 22,输出一行,即输入 22 的答案。

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
3
5

数据规模与约定

对于 100%100\% 的数据,m1.6×105m \le 1.6\times10^{5},询问数 Q104Q\le 10^4w2×106w\le 2\times 10^6

提示

保证答案不会超过 int 范围