Background

— s10

Problem Description

There are $n$ spikes on a plane, with all positions distinct. Each spike has one of $4$ directions: up, down, left, or right.

Define a “yin-jian spike” (阴间刺, literally “underworld spike”, actually a shaved sf spike) as an ordered triple of spikes $(s_1, s_2, s_3)$ that satisfies:

• $s_1$ faces right, $s_2$ faces left, and $s_3$ faces up.
• $x(s_1) < x(s_2) \leqslant x(s_3)$.
• $y(s_2) > y(s_1) > y(s_3)$.
• $x(s_2) - x(s_1) \leqslant d$.

Here, $x(s)$ and $y(s)$ denote the $x$-coordinate and $y$-coordinate of spike $s$, respectively. $d$ is kid’s width, and it is a constant within one test case.

The positive direction of the $x$-axis is from left to right, and the positive direction of the $y$-axis is from bottom to top.

The figures above show two examples of yin-jian spikes when $d \geqslant 2$. Although in the second spike shape, $s_3$ does not affect kid’s jump/oh

Given the positions and directions of $n$ spikes, tell kid how many yin-jian spikes (that he cannot jump over) there are.

Obviously, downward spikes are meaningless in this problem.

Input Format

This problem contains multiple test cases within a single input file.

The first line contains two positive integers $T, id$, representing the number of test cases and the testdata id. In particular, for the samples, $id=0$.

For each test case, the first line contains two positive integers $n, d$, representing the number of spikes and kid’s width. The next $n$ lines each contain two integers $x, y$ and a character $c$, describing the position and direction of one spike: U means up, D means down, L means left, and R means right.

Output Format

For each test case, output one line with one positive integer, the number of yin-jian spikes.

4 0
3 1
2 1 U
1 2 R
2 3 L
3 1
4 1 U
1 2 R
3 4 L
6 4
2 1 U
1 2 R
3 2 U
2 3 L
1 3 R
2 4 L
8 9
4 5 L
1 4 R
3 4 L
2 3 R
1 2 R
3 2 U
4 2 U
3 1 U

1
0
4
6

见附件中的 s4/ex.in

见附件中的 s4/ex.out

Hint

Constraints

This problem uses bundled subtasks.

$$\def\r{\cr\hline} \def\arraystretch{1.5} \begin{array}{c|c|c|c|c} \textbf{Subtask} & id= & {\sum n\leqslant} & \textbf{Other Constraints} & \textbf{Score}\r \textsf1 & 1\sim 7 & 3\times10^4 & n\leqslant 30 & 10 \r \textsf2 & 31\sim45 & 10^4 & - & 25 \r \textsf3 & 8\sim10,16\sim17 & 10^5 & d=10^9 & 20 \r \textsf4 & 18\sim20 & 3\times10^5 & d=1 & 10 \r \textsf5 & 11\sim15,21\sim30 & 3\times10^5 & - & 35 \r \end{array}$$

Here, $\sum n$ denotes the sum of all $n$ within one input file.

For $100\%$ of the data: $1\leqslant T\leqslant 2\times10^3$, $1\leqslant n\leqslant 3\times10^5$, $\sum n\leqslant 3\times10^5$, $1\leqslant d\leqslant 10^9$, $1\leqslant x,y\leqslant 10^9$, all $(x,y)$ are distinct, and $c\in\{\texttt U, \texttt D, \texttt L, \texttt R \}$.

Hint

For $\textbf{Sub}{\textsf2}$, both an $O(n^2\log n)$ approach and an $O(n^2)$ approach are worth thinking about. They may both give some hints…? qwq

Sample #1-1 & #1-2 Explanation

See the two figures in the Description.

Note that in #1-2, $d=1$, so kid can simply squeeze through the gap, and it does not count as yin-jian.

Sample #1-3 Explanation

The $4$ yin-jian spikes are: $\Big((1,3),(2,4),(2,1)\Big),\Big((1,2),(2,4),(2,1)\Big),\Big((1,2),(2,3),(2,1)\Big),\Big((1,3),(2,4),(3,2)\Big)$, i.e. $(5,6,1),(2,6,1),(2,4,1),(5,6,3)$ (the numbers are spike indices: $i$ means the $i$-th spike).

Sample #1-4 Explanation

The $6$ yin-jian spikes are $(2,1,7),(4,1,7),(4,3,6),(4,3,7),(4,3,8),(5,3,8)$.

For Sample #2, see the attachment. Besides $id=0$, this sample satisfies all constraints of $\text{Subtask }\textsf1$.

Translated by ChatGPT 5