CF978F Mentors

在 BerSoft 公司有 $n$ 名程序员，第 $i$ 名程序员的能力值为 $r_i$。 如果程序员 $a$ 的能力值严格大于程序员 $b$ 的能力值（即 $r_a > r_b$），并且 $a$ 和 $b$ 之间没有争吵，那么程序员 $a$ 可以成为程序员 $b$ 的导师。 现在给出每位程序员的能力值，以及 $k$ 对有争吵关系的程序员（每对是无序的）。对于每位程序员 $i$，请你计算有多少名程序员可以成为 $i$ 的被指导者（即 $i$ 可以成为他们的导师）。

第一行包含两个整数 $n$ 和 $k$，表示程序员总数和有争吵关系的程序员对数（$2 \le n \le 2 \cdot 10^5$，$0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$）。 第二行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$（$1 \le r_i \le 10^{9}$），其中 $r_i$ 表示第 $i$ 名程序员的能力值。 接下来的 $k$ 行，每行包含两个不同的整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \ne y$），表示第 $x$ 名和第 $y$ 名程序员之间有争吵关系。每对关系是无序的，即如果 $x$ 和 $y$ 有争吵，则 $y$ 和 $x$ 也有争吵。保证每对 $(x, y)$ 在输入中只出现一次，且不会出现 $(x, y)$ 和 $(y, x)$ 同时出现。

输出 $n$ 个整数，第 $i$ 个数表示第 $i$ 名程序员可以成为导师的程序员数量。程序员的编号顺序与输入的能力值顺序一致。

在第一个样例中，第一名程序员不能成为任何人的导师（因为只有第二名程序员的能力值比第一名低，但他们有争吵关系）。第二名程序员不能成为任何人的导师，因为他的能力值是最小的。第三名程序员可以成为第二名程序员的导师。第四名程序员可以成为第一名和第二名程序员的导师，但不能成为第三名程序员的导师，因为他们有争吵关系。 由 ChatGPT 4.1 翻译