P16704 [SEATST 2026] 国家排行 / Country Ranks
题目描述
SEATST 比赛共有 $N$ 名学生参加。每名学生代表一个国家。比赛结束后，所有学生获得了**互不相同**的分数。
Prabowo 准备在官网上发布排行榜。对于每位学生，排行榜上列出了他们的国家、分数、总排名（global rank）和国内排名（country rank）。
- 一名学生的总排名的定义为分数高于该学生的人数。
- 一名学生的**国内排名**定义为与该学生同属一个国家且分数高于该学生的人数。
排行榜的示例如下：
| 国家 | 分数 | 总排名 | 国内排名 |
|:-:|:-:|:-:|:-:|
| 新加坡 (Singapore) | $574$ | $0$ | $0$ |
| 马来西亚 (Malaysia) | $483$ | $1$ | $0$ |
| 新加坡 (Singapore) | $466$ | $2$ | $1$ |
| 印度尼西亚 (Indonesia) | $460$ | $3$ | $0$ |
| 新加坡 (Singapore) | $458$ | $4$ | $2$ |
| 马来西亚 (Malaysia) | $454$ | $5$ | $1$ |
| 新加坡 (Singapore) | $448$ | $6$ | $3$ |
| 马来西亚 (Malaysia) | $440$ | $7$ | $2$ |
| 印度尼西亚 (Indonesia) | $438$ | $8$ | $1$ |
请注意，总排名和国内排名均从 $0$ 开始，且排名不会跳号（无论是总排名还是国内排名）。
然而，当排行榜上传到网上时，Prabowo 忘记公布学生的国家和分数。对于每位学生，我们只知道他们的总排名和国内排名。
Prabowo 试图挽救这一局面，并交给你一个任务，帮助他计算以下两个数量：
- 必定属于**同一个**国家的学生对的数量，以及
- 必定属于**不同**国家的学生对的数量。
:::warning[警告]{open}
如果存在两种满足总排名和国内排名的分配方案，使得两名学生在其中一种方案中属于同一个国家，而在另一种方案中属于两个不同的国家，那么这对学生不应被计入上述任何一种计算中。
:::
请帮助 Prabowo!
### 实现详情
你需要实现以下两个函数。
```cpp
long long count_same_country(int N, std::vector country_rank)
long long count_diff_country(int N, std::vector country_rank)
```
- $N$ ：学生人数。
- `country_rank`：一个长度为 $N$ 的数组，表示国内排名。对于所有 $0 \le i \le N - 1$ ， `country_rank[i]` 是总排名为 $i$ 的学生的国内排名。
第一个函数应返回不同学生的无序对的数量，并且每对学生都应满足在所有与排行榜相符的学生国家分配方案中均都属于同一个国家。
第二个函数应返回不同学生的无序对的数量，并且每对学生都应满足在所有与排行榜相符的学生国家分配方案中均都属于不同国家。
在每个测试数据中，这两个函数最多各被调用一次。
输入格式
输入格式：
```
N X
C[0] C[1] ... C[N-1]
```
这里的 `X` 可以是字符串 `same`（相同）或 `diff`（不同），从而构成 `count_X_country` 函数调用，且对于所有 $0 \le i \le N - 1$ ， `C[i]` 表示 `country_rank[i]`。
输出格式
一个整数表示 `count_X_country` 的输出结果。
说明/提示
### 样例
考虑以下函数调用：
```cpp
count_same_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])
```
假设学生 $0$、$1$ 和 $3$（为了方便起见，这里我们用学生的总排名对其进行编号）分别代表新加坡、马来西亚和印度尼西亚。
那么，下表列出了所有可能产生该排名的所有方案：
| 总排名 | 国内排名 | 方案 1 | 方案 2 | 方案 3 | 方案 4 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| $0$ | $0$ | 新加坡 | 新加坡 | 新加坡 | 新加坡 |
| $1$ | $0$ | 马来西亚 | 马来西亚 | 马来西亚 | 马来西亚 |
| $2$ | $1$ | 新加坡 | 新加坡 | 马来西亚 | 马来西亚 |
| $3$ | $0$ | 印度尼西亚 | 印度尼西亚 | 印度尼西亚 | 印度尼西亚 |
| $4$ | $2$ | 新加坡 | 新加坡 | 马来西亚 | 马来西亚 |
| $5$ | $1$ | 马来西亚 | 印度尼西亚 | 新加坡 | 印度尼西亚 |
| $6$ | $3$ | 新加坡 | 新加坡 | 马来西亚 | 马来西亚 |
| $7$ | $2$ | 马来西亚 | 印度尼西亚 | 新加坡 | 印度尼西亚 |
| $8$ | $1$ | 印度尼西亚 | 马来西亚 | 印度尼西亚 | 新加坡 |
有 $4$ 对学生必定始终属于同一个国家：$(2, 4)$、$(2, 6)$、$(4, 6)$ 和 $(5, 7)$。因此，此函数应返回 $4$。
`count_diff_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])`
有 $17$ 对学生必定始终属于不同国家：$(0, 1)$、$(0, 3)$、$(1, 3)$、$(2, 3)$、$(2, 5)$、$(2, 7)$、$(2, 8)$、$(3, 4)$、$(3, 6)$、$(4, 5)$、$(4, 7)$、$(4, 8)$、$(5, 6)$、$(5, 8)$、$(6, 7)$、$(6, 8)$、$(7, 8)$。因此，此函数应返回 $17$。
`count_same_country(5, [0, 1, 0, 1, 2])`
此处有 $2$ 对学生必定始终属于同一个国家：$(0, 1)$ 和 $(2, 3)$。因此，此函数应返回 $2$。
`count_diff_country(5, [0, 1, 0, 1, 2])`
有 $4$ 对学生必定属于两个不同的国家：$(0, 2)$、$(0, 3)$、$(1, 2)$、$(1, 3)$。因此，此函数应返回 $4$。
### 约束
- $1 \le N \le 1\ 000\ 000$。
- 保证存在至少一种满足 `country_rank` 的学生国家分配方案。
### 子任务
对于前 $6$ 个子任务，只会调用 `count_same_country` 。
1. （$3$ 分） $N \le 8$。
2. （$6$ 分） `country_rank` 最多包含两个 $0$。
3. （$6$ 分） `country_rank` 不包含 $2$。
4. （$3$ 分） $N \le 300$。
5. （$3$ 分） $N \le 2000$。
6. （$9$ 分）没有额外的约束。
对于后 $6$ 个子任务，只会调用 `count_diff_country` 。
7. （$7$ 分） $N \le 8$。
8. （$14$ 分） `country_rank` 最多包含两个 $0$。
9. （$14$ 分） `country_rank` 不包含 $2$。
10. （$7$ 分） $N \le 300$。
11. （$7$ 分） $N \le 2000$。
12. （$21$ 分）没有额外的约束。