Minecraft Series

题意翻译

## 题意翻译 ### 题目描述 小 Misha 参加了编程社，但是一道题也没有做出来。这件事看上去有些匪夷所思，但你发现 Misha 正在摄制一部《我的世界》剧集时，一切就都说得通了。 Misha 受到曼哈顿地区道路的启发，在《我的世界》里建造了一座城市，其可以视为一个 $n \times m$ 的表格。城里住着 $k$ 名学生，其中第 $i$ 名学生住在第 $x_i$ 行和第 $y_i$ 列的交叉处，每名学生都有一个易怒值 $w_i$。由于城市的规模很大，Misha 决定将剧集的故事情节限制在发生于某个正方形区域 $s$ 中，其各边均与坐标轴平行。正方形区域的边长应当是一个 $\geqslant 1$ 且 $\leqslant \min(n, m)$ 的整数。 根据情节，主角将会来到这座城市并意外进入正方形区域 $s$ 里。主角的易怒值为 $0$，所以他可以利用自己的领导才能召集一个由平静、不温不火和易怒的学生们组成的团队。 为了使团队有机动性并团结紧密，团队中所有学生的易怒值必须各不相同且必须能够组成一条连续的序列。形式上说，如果存在有学生的易怒值可以组成一条形如 $ l, l+1, \ldots, -1, 1, \ldots, r-1, r $ 的序列，其中 $ l \le 0 \le r $，那么主角就能召集一个由 $r - l + 1$ 人组成的团队（主角自己也在团队中）。 请注意，不一定要把正方形区域 $s$ 内的所有学生都加入团队。 Misha 觉得这个团队至少应该容纳 $t$ 人。他很想知道：这个表格里有多少个正方形区域可供主角召集一个团队？请帮他算一算。 ### 输入格式 第一行分别是四个整数 $n$、$m$、$k$ 和 $t$（$ 1 \leqslant n, m \leqslant 40\,000 $，$ 1 \leqslant n \cdot m \leqslant 40\, 000 $，$ 1 \leqslant k \leqslant 10^6 $，$ 1 \leqslant t \leqslant k + 1 $），分别代表表格里的行数、列数，城市里学生的总数和一个团队的人数下限。 接下来的 $k_i$ 行，每行有三个整数 $x_i$、$y_i$ 和 $w_i$（$ 1 \leqslant x_i \leqslant n $，$ 1 \leqslant y_i \leqslant m $，$ 1 \leqslant \lvert w_i \rvert \leqslant 10^9 $），分别代表第 $i$ 名学生居住在的行数、列数以及他的易怒值。 ### 输出格式 一行一个整数，表格里可供主角召集一个团队的正方形区域的总数。 ### 样例说明 1. 在样例一中，如图，主角无法在任何正方形区域 $s$ 中召集到至少包含 $2$ 人的团队。 2. 在样例二中，如图，主角有两种召集团队的方式： 1. 成员易怒值分别为 $\left [0, 1 \right ]$； 2. 成员易怒值分别为 $\left [ 0, 1, 2 \right ]$。 注意，无论哪种方式，主角的易怒值 $0$ 都会被包含在团队中。 3. 在样例三中，如图，主角有四种召集团队的方式： 1. 成员易怒值分别为 $\left [-1, 0, 1 \right ]$； 2. 成员易怒值分别为 $\left [0, 1 \right ]$； 3. 成员易怒值分别为 $\left [0, 1 \right ]$； 4. 成员易怒值分别为 $\left [-1, 0, 1 \right ]$。

题目描述

Little Misha goes to the programming club and solves nothing there. It may seem strange, but when you find out that Misha is filming a Minecraft series, everything will fall into place... Misha is inspired by Manhattan, so he built a city in Minecraft that can be imagined as a table of size $ n \times m $ . $ k $ students live in a city, the $ i $ -th student lives in the house, located at the intersection of the $ x_i $ -th row and the $ y_i $ -th column. Also, each student has a degree of his aggressiveness $ w_i $ . Since the city turned out to be very large, Misha decided to territorially limit the actions of his series to some square $ s $ , which sides are parallel to the coordinate axes. The length of the side of the square should be an integer from $ 1 $ to $ \min(n, m) $ cells. According to the plot, the main hero will come to the city and accidentally fall into the square $ s $ . Possessing a unique degree of aggressiveness $ 0 $ , he will be able to show his leadership qualities and assemble a team of calm, moderate and aggressive students. In order for the assembled team to be versatile and close-knit, degrees of aggressiveness of all students of the team must be pairwise distinct and must form a single segment of consecutive integers. Formally, if there exist students with degrees of aggressiveness $ l, l+1, \ldots, -1, 1, \ldots, r-1, r $ inside the square $ s $ , where $ l \le 0 \le r $ , the main hero will be able to form a team of $ r-l+1 $ people (of course, he is included in this team). Notice, that it is not required to take all students from square $ s $ to the team. Misha thinks that the team should consist of at least $ t $ people. That is why he is interested, how many squares are there in the table in which the main hero will be able to form a team of at least $ t $ people. Help him to calculate this.

输入输出格式

输入格式

The first line contains four integers $ n $ , $ m $ , $ k $ and $ t $ ( $ 1 \le n, m \le 40\,000 $ , $ 1 \le n \cdot m \le 40\,000 $ , $ 1 \le k \le 10^6 $ , $ 1 \le t \le k + 1 $ ) — the number of rows and columns in the table, and the number of students living in the city, respectively. Each of the following $ k $ lines contains three integers $ x_i $ , $ y_i $ and $ w_i $ ( $ 1 \le x_i \le n $ , $ 1 \le y_i \le m $ , $ 1 \le \lvert w_i \rvert \le 10^9 $ ) — the number of row and column, where the $ i $ -th student is living, and the degree of his aggressiveness.

输出格式

Print one integer — the number of ways to choose the square $ s $ in such way that the main hero will be able to form a team of at least $ t $ people.

输入输出样例

输入样例 #1

2 2 1 2
1 1 2

输出样例 #1

0

输入样例 #2

2 2 2 2
1 1 1
2 2 2

输出样例 #2

2

输入样例 #3

2 2 4 2
1 1 1
1 1 -1
1 2 1
2 2 1

输出样例 #3

4

说明

1. In the first example the main hero will not be able to form a team of more than one person in any square $ s $ . Illustration for the first example. 2. In the second example there are two ways to select square $ s $ . Both of them are illustrated below. In one of them the main hero will be able to form a team of students with degrees of aggressiveness $ [0, 1] $ , and in the another — with degrees of aggressiveness $ [0, 1, 2] $ . Notice, that the main hero with degree of aggressiveness $ 0 $ will be included to the team regardless of the chosen square. Illustration for the second example. 3. In the third example there are four ways to select square $ s $ . All of them are illustrated below. The main hero will be able to form a team with degrees of aggressiveness: $ [-1,0,1] $ , $ [0,1] $ , $ [0,1] $ , $ [-1, 0, 1] $ , respectively. Illustration for the third example.

**题目大意：**
小 Misha 参加 Minecraft 编程社活动，但他没有做出任何题目。然而，当发现他正在制作《我的世界》剧集时，这一切就变得合理了。Misha 在游戏中建造了一座城市，可以看作是一个 $n \times m$ 的网格。城市中有 $k$ 名学生，第 $i$ 名学生住在第 $x_i$ 行和第 $y_i$ 列的交叉处，每名学生都有一个易怒值 $w_i$。由于城市很大，Misha 决定将剧情限制在某个边长为正整数且 $\geqslant 1$ 且 $\leqslant \min(n, m)$ 的正方形区域 $s$ 中，区域边与坐标轴平行。主角的易怒值为 $0$，可以召集一个由平静、不温不火和易怒的学生组成的团队。团队中所有学生的易怒值必须各不相同且能组成一条连续的序列。Misha 希望团队至少有 $t$ 人，问题是：有多少个正方形区域可供主角召集团队？

**输入格式：**
第一行包含四个整数 $n, m, k, t$（$1 \leqslant n, m \leqslant 40,000$, $1 \leqslant n \cdot m \leqslant 40,000$, $1 \leqslant k \leqslant 10^6$, $1 \leqslant t \leqslant k + 1$），分别代表网格的行数、列数，城市中学生的总数和团队人数下限。接下来 $k$ 行，每行三个整数 $x_i, y_i, w_i$（$1 \leqslant x_i \leqslant n$, $1 \leqslant y_i \leqslant m$, $1 \leqslant |w_i| \leqslant 10^9$），代表第 $i$ 名学生的居住行数、列数和易怒值。

**输出格式：**
输出一个整数，表示主角可以召集团队的正方形区域总数。

**样例说明：**
1. 在样例一中，主角无法在任何正方形区域 $s$ 中召集至少 $2$ 人的团队。
2. 在样例二中，有两种召团队的方式，分别对应易怒值序列 $\left [0, 1 \right ]$ 和 $\left [ 0, 1, 2 \right ]$。
3. 在样例三中，有四种召团队的方式，分别对应易怒值序列 $\left [-1, 0, 1 \right ]$、$\left [0, 1 \right ]$、$\left [0, 1 \right ]$ 和 $\left [-1, 0, 1 \right ]$。**题目大意：** 小 Misha 参加 Minecraft 编程社活动，但他没有做出任何题目。然而，当发现他正在制作《我的世界》剧集时，这一切就变得合理了。Misha 在游戏中建造了一座城市，可以看作是一个 $n \times m$ 的网格。城市中有 $k$ 名学生，第 $i$ 名学生住在第 $x_i$ 行和第 $y_i$ 列的交叉处，每名学生都有一个易怒值 $w_i$。由于城市很大，Misha 决定将剧情限制在某个边长为正整数且 $\geqslant 1$ 且 $\leqslant \min(n, m)$ 的正方形区域 $s$ 中，区域边与坐标轴平行。主角的易怒值为 $0$，可以召集一个由平静、不温不火和易怒的学生组成的团队。团队中所有学生的易怒值必须各不相同且能组成一条连续的序列。Misha 希望团队至少有 $t$ 人，问题是：有多少个正方形区域可供主角召集团队？ **输入格式：** 第一行包含四个整数 $n, m, k, t$（$1 \leqslant n, m \leqslant 40,000$, $1 \leqslant n \cdot m \leqslant 40,000$, $1 \leqslant k \leqslant 10^6$, $1 \leqslant t \leqslant k + 1$），分别代表网格的行数、列数，城市中学生的总数和团队人数下限。接下来 $k$ 行，每行三个整数 $x_i, y_i, w_i$（$1 \leqslant x_i \leqslant n$, $1 \leqslant y_i \leqslant m$, $1 \leqslant |w_i| \leqslant 10^9$），代表第 $i$ 名学生的居住行数、列数和易怒值。 **输出格式：** 输出一个整数，表示主角可以召集团队的正方形区域总数。 **样例说明：** 1. 在样例一中，主角无法在任何正方形区域 $s$ 中召集至少 $2$ 人的团队。 2. 在样例二中，有两种召团队的方式，分别对应易怒值序列 $\left [0, 1 \right ]$ 和 $\left [ 0, 1, 2 \right ]$。 3. 在样例三中，有四种召团队的方式，分别对应易怒值序列 $\left [-1, 0, 1 \right ]$、$\left [0, 1 \right ]$、$\left [0, 1 \right ]$ 和 $\left [-1, 0, 1 \right ]$。