Rainbow Rectangles
Contest: Codeforces Round 666 (Div. 1)
Difficulty rating: 3300
Tags: data structures, sortings, two pointers

Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a $$$L \times L$$$ grid. There are $$$n$$$ M&M candies on the grid, the $$$i$$$-th M&M is currently located at $$$(x_i + 0.5, y_i + 0.5),$$$ and has color $$$c_i$$$ out of a total of $$$k$$$ colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex $$$(X_1, Y_1)$$$ and right-top vertex $$$(X_2, Y_2)$$$ are points with integer coordinates satisfying $$$0 \le X_1 < X_2 \le L$$$ and $$$0 \le Y_1 < Y_2 \le L$$$, so that for every color $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$ that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo $$$10^9 + 7$$$.

Input format:
The first line contains three positive integers $$$n, k, L$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^3, 1 \leq L \leq 10^9 )$$$ — the number of M&Ms, the number of colors and the length of the grid respectively.

The following $$$n$$$ points describe the M&Ms. Each line contains three integers $$$x_i, y_i, c_i$$$ $$$(0 \leq x_i, y_i < L, 1 \le c_i \le k)$$$ — the coordinates and color of the $$$i$$$-th M&M respectively.

Different M&Ms have different coordinates ($$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$ for every $$$i \ne j$$$), and for every $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$.

Output format:
Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Grid for the first sample:

Example input:
4 2 4
3 2 2
3 1 1
1 1 1
1 2 1

Example output:
20

Example input:
5 3 10
6 5 3
5 3 1
7 9 1
2 3 2
5 0 2

Example output:
300

Editorial:
Let $$$xl, xr, yd, yu$$$ denote a rectangle with opposite corners $$$(xl, yd)$$$ and $$$(xr, yu)$$$. For convenience, assume $$$(xl \le xr)$$$ and $$$(yd \le yu)$$$.
Let's try solving the problem if coordinates are in range $$$[1, n]$$$. We could easily do this by coordinates compression.
First, let's look at the problem with $$$(yd, yu)$$$ fixed. We define $$$f_x$$$ to be the smallest integer such that $$$x \le f_x$$$ and $$$(x, yd), (f_x, yu)$$$ is a $$$\textbf{good}$$$ rectangle (If there is no such integer, let $$$f_x = inf$$$). It can be proven that $$$f_x$$$ is non-decreasing, i.e. if $$$x < y$$$, then $$$f_x \le f_y$$$.
Now, let's see how $$$f_x$$$ changes when we iterate $$$yd$$$ over a fixed $$$yu$$$. It is hard to add points to the set, so we will try to support deleting points operation. For point $$$i$$$, we have the following definitions:
Let set $$$S = \{ j | c_j = c_i, y_i < y_j \le yu, x_j \le x_i \}$$$. Let $$$prv_i = j \in S$$$ with the largest $$$x_j$$$.
Let set $$$S' = \{ j | c_j = c_i, y_i < y_j \le yu, x_j \ge x_i \}$$$. Let $$$nxt_i = j \in S'$$$ with the smallest $$$x_j$$$.
(Note that $$$S$$$ or $$$S'$$$ might represent empty set).
With these two functions, we could see how $$$f_x$$$ changes after we delete point $$$i$$$. It looks something like this: For every $$$xl \in (x_{prv_i}, x_i]$$$ such that $$$f_{xl} \ge x_i, f_{xl} = max(f_{xl}, x_{nxt_i})$$$;
We could support this operation using segment tree with lazy propagation. The total time complexity is $$$O(n^2 \cdot log_n)$$$.