3519. [USACO20Dec Silver]Stuck in a Rut

【题目描述】

Farmer John 最近扩大了他的农场，从奶牛们的角度看来这个农场相当于是无限大了！奶牛们将农场上放牧的区域想作是一个由正方形方格组成的无限大二维方阵，每个方格中均有美味的草（将每个方格看作是棋盘上的一个方格）。Farmer John 的 $N$ 头奶牛（$1\le N\le 1000$）初始时位于不同的方格中，一部分朝向北面，一部分朝向东面。

每一小时，每头奶牛会执行以下二者之一：

• 如果她当前所在的方格里的草已经被其他奶牛吃掉了，则她会停下（并从这个时刻开始一直保持停止）。
• 吃完她当前所在的方格中的所有草，并向她朝向的方向移动一个方格。

经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。

如果两头奶牛在一次移动中移动到了同一个有草的方格，她们会分享这个方格中的草，并在下一个小时继续沿她们朝向的方向移动。

当 Farmer John 看到停止吃草的奶牛时会不高兴，他想要知道谁该为他停止吃草的奶牛受到责备。如果奶牛 $b$ 停在了之前奶牛 $a$ 吃过草的一个方格，我们就称奶牛 $a$ 阻碍了奶牛 $b$。进一步地，如果奶牛 $a$ 阻碍了奶牛 $b$ 且奶牛 $b$ 阻碍了奶牛 $c$，我们认为奶牛 $a$ 也阻碍了奶牛 $c$（也就是说，「阻碍」关系具有传递性）。每头奶牛受到责备的程度与这头奶牛阻碍的奶牛数量一致。请计算每头奶牛受到责备的数量——也就是说，每头奶牛阻碍的奶牛数量。

【输入格式】

输入的第一行包含 $N$。以下 $N$ 行，每行描述一头奶牛的起始位置，包含一个字符 N（表示朝向北面） 或 E（表示朝向东面），以及两个非负整数 $x$ 和 $y$（$0\le x\le 10^9$，$0\le y\le 10^9$）表示方格的坐标。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。

为了使方向和坐标尽可能明确，如果一头奶牛位于方格 $(x,y)$ 并向北移动，她会到达方格 $(x,y+1)$。如果她向东移动，她会到达方格 $(x+1, y)$。

【输出格式】

输出 $N$ 行。输出的第 $i$ 行包含输入中的第 $i$ 头奶牛受到的责备的数量。

【样例输入】

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 1
E 9 2

【样例输出】

0
0
1
2
1
0

【样例说明】

在这个样例中，奶牛 3 阻碍了奶牛 2，奶牛 4 阻碍了奶牛 5，奶牛 5 阻碍了奶牛 6。根据传递性，奶牛 4 也阻碍了奶牛 6。

【数据规模与约定】

对于$ 50\% $的测试数据(测试点$ 1\sim5 $)，所有坐标不超过 $2000$。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Silver 组