CF978F · Mentors

• 难度：1500
• 标签：binary search、data structures、implementation
• 链接：https://codeforces.com/problemset/problem/978/F
• 时间限制：3 seconds　内存限制：256 megabytes
• 出现位置：Day27-阶段模拟6-S T1T2稳分卷

中文题意

BerSoft 公司有 $n$ 名程序员，第 $i$ 名程序员的能力值为 $r_i$。

程序员 $a$ 可以成为程序员 $b$ 的导师，当且仅当 $a$ 的能力值严格大于 $b$ 的能力值（$r_a > r_b$），且 $a$ 与 $b$ 之间没有闹矛盾。

给定每名程序员的能力值以及 $k$ 对处于矛盾中的程序员（每对无序）。对每名程序员 $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$ 有矛盾则 $y$ 与 $x$ 也有矛盾。保证每对 $(x, y)$ 不会以 $(x, y)$ 或 $(y, x)$ 的形式在输入中重复出现。

输出格式（中文）

输出 $n$ 个整数，第 $i$ 个数为第 $i$ 名程序员能够担任导师的程序员数目。程序员的编号顺序与输入中能力值给出的顺序相同。

样例

样例 1

输入：

4 2
10 4 10 15
1 2
4 3

输出：

0 0 1 2 

样例 2

输入：

10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5

输出：

5 4 0 5 3 3 9 0 2 5