[Ynoi2004] tars2
题目描述
你需要维护平面上的整点,每个点初始有点权 $0$,共 $m$ 次操作。
修改操作:给定 $x,y,d,w$,将满足 $|X-x|<d,|Y-y|<d$ 的整点 $(X,Y)$ 的点权增加 $w\cdot(d-\max(|X-x|,|Y-y|))$;
查询操作:给定 $x_1,x_2,y_1,y_2$,查询满足 $x_1\le X\le x_2,\;y_1\le Y\le y_2$ 的整点 $(X,Y)$ 的点权之和,答案对 $2^{30}$ 取模。
输入输出格式
输入格式
第一行一个整数 $m$,接下来 $m$ 行,每行表示一个操作。
修改操作表示为 `1 x y d w`;
查询操作表示为 `2 x1 x2 y1 y2`。
输出格式
对每个查询操作,输出一行,包含一个整数,表示取模后的答案。
输入输出样例
输入样例 #1
5
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5
1 4 4 4 8
输出样例 #1
46
21
说明
Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078
对于 $100\%$ 的数据,满足 $1\le m\le 10^5$,$1\le x_1\le x_2\le {10}^8$,$1\le y_1\le y_2\le {10}^8$,$1\le x,y,d,w\le {10}^8$。