P9434 [NAPC-#1] Stage4 - Needle

>  > > — s10

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.

**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.

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

### 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