思路

由于题目中给出了所有 $x$ 都不相同，所有的 $y$ 也不相同，那么我们发现，只有两个不同方向的奶牛才有相交的可能。

所以，我们为了方便，在输入的时候直接把奶牛给分成两组，然后两层循环遍历一下，记录所有有可能发生的路径相交。

由于奶牛只往右或者上走，所以对于一直奶牛，最靠左下的那一次相交时最先发生的。

然后就可u有直接计算了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
N：x 坐标不变
E：y 坐标不变
*/
int n;
struct node {
    int x, y, ca, cb, t; 
};
bool cmp(node x, node y) {
    if (x.x == y.x) return x.y < y.y;
    else return x.x < y.x;
}
vector <node> v;
struct cow {
    char face;
    int x, y;
} a[1000005];
int b[1000005];
int nn[1000005], ee[1000005], cnte, cntn;
int cnt[1000005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].face >> a[i].x >> a[i].y;
        if (a[i].face == 'N') nn[++cntn] = i;
        else ee[++cnte] = i;
    }
    for(int i = 1; i <= cntn; i++){
        for(int j = 1; j <= cnte; j++){
            if(a[nn[i]].x > a[ee[j]].x && a[nn[i]].y < a[ee[j]].y){
                v.push_back((node){a[nn[i]].x, a[ee[j]].y, ee[j], nn[i]});
            }
        }
    }
//  for (int i = 1; i <= n; i ++) {
//      for (int j = 1; j <= n; j ++) {
//          if (a[i].face == 'N') {
//              if (a[j].face == 'E') {
//                  if (a[i].x > a[j].x && a[i].y < a[j].y) {
//                      if (a[i].x - a[j].x > a[j].y - a[i].y) v.push_back((node){a[i].x, a[j].y, i, j, a[j].y - a[i].y});
//                      else v.push_back((node){a[i].x, a[j].y, j, i, a[i].x - a[j].x});
//                  }
//              }
//              else if (a[i].y != a[j].y && a[i].x == a[j].x) {
//                  if (a[i].y > a[j].y) v.push_back((node){a[i].x, a[i].y, i, j, a[i].y - a[j].y});
//                  else v.push_back((node){a[j].x, a[j].y, j, i, a[j].y - a[j].y});
//              }
//          }
//          else 
//      }
//  }
    sort(v.begin(), v.end(), cmp);
    for (auto x : v) {
        if (b[x.ca] || b[x.cb]) {
            continue;
        }
        int dx = x.x - a[x.ca].x;
        int dy = x.y - a[x.cb].y;
        if (dx > dy) {
            b[x.ca] = x.cb;
            cnt[x.cb] += cnt[x.ca] + 1;
        } else if (dx < dy) {
            b[x.cb] = x.ca;
            cnt[x.ca] += cnt[x.cb] + 1;
        }

    }
    for (int i = 1; i <= n; i ++) {
        cout << cnt[i] << "\n";
    }
    return 0;
}