3968. 新式武器

【题目背景】

邪恶的帝国主义国家A国发明了一种新式的化学武器，该化学武器会污染打击的地区，为了测试武器的效果，它们选择了一块实验场地。

【题目描述】

实验场地是一个面积为$m\times n$的矩形，被分割成了大小相同的$m$行$n$列的方格，每个方格都有一个由行和列组成的坐标，左上角的坐标为$(1,1)$，右下角的坐标为$(m,n)$。

A国共进行的$T$次测试，每次测试都会选择在某一个坐标$(x,y)$处投放，且该新式武器可以任意调整攻击范围$k$，该武器会污染所有到$(x,y)$的曼哈顿距离小于等于$k$的方格。曼哈顿距离的定义：两个点$(x_1,y_1),(x_2,y_2)$的曼哈顿距离为$|x_1-x_2|+|y_1-y_2|$。

现在A国准备进行$T$次打击，它想统计打击之后污染的土地面积。

【输入格式】

第一行输入三个正整数， $m,n,T$，分表表示实验场地的大小和测试进行的次数。

接下来$T$行，每行三个整数$x,y,k$，表示在$(x,y)$处投放一个攻击范围为$k$的武器。

【输出格式】

一行一个整数，表示$T$次打击结束后污染的土地面积。

【样例1输入】

10 10 4
4 2 4
3 9 0
7 5 2
10 10 3

【样例2输出】

52

【样例2/3】

样例下载

【样例说明】

实验场地大小为$10\times 10$， 共有$4$次打击。

第$1$次打击坐标为$(4,2)$，攻击范围为$4$。

第$2$次打击坐标为$(3,9)$，攻击范围为$0$，也即只会污染$(3,9)$。

第$3$次打击坐标为$(7,5)$，攻击范围为$2$。

第$4$次打击坐标为$(10,10)$，攻击范围为$3$。

【数据规模与约定】

对于$10\%$的数据，$1\leq m,n\leq 100, 1\leq T\leq 100, 0\leq k\leq 10$。

对于$30\%$的数据，$1\leq m,n\leq 5000, 1\leq T\leq 500, 0\leq k\leq 100$。

另有$10\%$的数据，有$k=0$。

另有$20\%$的数据，有$m=1$或$n=1$。

对于$100\%$的数据，$1\leq m,n\leq 5000, 1\leq T\leq 10^4, 1\leq x\leq m,1\leq y\leq n, 0\leq k\leq 500$。

【来源】

2024年校际联合邀请赛 入门组-第1场 Task2