A5848. 「JSOI2019」精准预测
编程题
NOI/NOI+/CTSC
知识点
题目描述
#### 题目背景
JYY 和他的火星探险队再次登录火星小镇，并且打算把机器学习的知识传授给火星人，从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。为了让火星人彻底信服，JYY 的探险队找到了他们之前关于火星详细的数据记录，并且训练了一个预测模型，这个模型能准确地预测出火星人在未来的生死情况。
#### 题目描述
目前，火星小镇上有 $n$ 个居民（编号 $1, 2, \ldots, n$）。机器学习算法预测出这些居民在接下来 $T$ 个时刻（编号 $1, 2, \ldots , T$）的生死情况，每条预测都是如下两种形式之一：
- **难兄难弟** $0\ t\ x\ y$：在 $t$ 时刻，如果 $x$ 是死亡状态，那么在 $t + 1$ 时刻，$y$ 是死亡状态。（注意，当 $x$ 在 $t$ 时刻是生存状态时，该预测也被认为是正确的）；
- **死神来了** $1\ t\ x\ y$：在 $t$ 时刻，如果 $x$ 是生存状态，那么在 $t$ 时刻，$y$ 是死亡状态。（注意，当 $x$ 在 $t$ 时刻是死亡状态时，该预测也被认为是正确的）。
注意本题是对某个时刻进行生死状态的预测，如果某个人在 $t$ 时刻是生存状态，在 $t + 1$ 时刻是死亡状态，你可以认为是在 $t$ 到 $t + 1$ 这段时间内发生了某个事件导致其死亡。
虽然 JYY 对自己从大数据中统计得到的模型非常自信，但火星人看到这些预测吓了一跳，表示实在难以接受这种设定，更是认为计算机科学是可怕的邪教，打破了他们平静的生活。为了安抚火星人的情绪， JYY 打算从这些预测结果中推导出一些火星人更容易接受的事实，从而安抚火星人的情绪。
具体来说，JYY 首先**假设对火星人生死的预测全部正确**，在此基础上，JYY 希望为小镇上的每个居民 $k$ **分别计算有多少个火星人有可能和他一起活到第** $T+1$ 时刻，换言之，JYY 希望为每个火星人 $k$ 计算
$$\sum_{1\le i\le n,i\neq k} \text{Live}(k,i)$$
其中 $\text{Live}(i, j) = 1$ 表示编号为 $i$ 和 $j$ 的火星人有可能同时在第 $T + 1$ 时刻处于生还状态，否则 $\text{Live}(i, j) = 0$。
注意火星人是不能够复活的。一个火星人可能在时刻 $1$ 就处于死亡状态，也有可能有**预测未覆盖的死亡**情况发生（火星人在任何时候都可能死亡，但任意时刻观察到火星人的状态要么活着，要么死亡）。最后，注意到 $\text{Live}$ 是为每一对火星人**分别独立计算的**，因此 $\text{Live}(x, y) = \text{Live}(y, z) = 1$ 并不意味着 $\text{Live}(x, z) = 1$。
JYY 和他的火星探险队再次登录火星小镇，并且打算把机器学习的知识传授给火星人，从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。为了让火星人彻底信服，JYY 的探险队找到了他们之前关于火星详细的数据记录，并且训练了一个预测模型，这个模型能准确地预测出火星人在未来的生死情况。
#### 题目描述
目前，火星小镇上有 $n$ 个居民（编号 $1, 2, \ldots, n$）。机器学习算法预测出这些居民在接下来 $T$ 个时刻（编号 $1, 2, \ldots , T$）的生死情况，每条预测都是如下两种形式之一：
- **难兄难弟** $0\ t\ x\ y$：在 $t$ 时刻，如果 $x$ 是死亡状态，那么在 $t + 1$ 时刻，$y$ 是死亡状态。（注意，当 $x$ 在 $t$ 时刻是生存状态时，该预测也被认为是正确的）；
- **死神来了** $1\ t\ x\ y$：在 $t$ 时刻，如果 $x$ 是生存状态，那么在 $t$ 时刻，$y$ 是死亡状态。（注意，当 $x$ 在 $t$ 时刻是死亡状态时，该预测也被认为是正确的）。
注意本题是对某个时刻进行生死状态的预测，如果某个人在 $t$ 时刻是生存状态，在 $t + 1$ 时刻是死亡状态，你可以认为是在 $t$ 到 $t + 1$ 这段时间内发生了某个事件导致其死亡。
虽然 JYY 对自己从大数据中统计得到的模型非常自信，但火星人看到这些预测吓了一跳，表示实在难以接受这种设定，更是认为计算机科学是可怕的邪教，打破了他们平静的生活。为了安抚火星人的情绪， JYY 打算从这些预测结果中推导出一些火星人更容易接受的事实，从而安抚火星人的情绪。
具体来说，JYY 首先**假设对火星人生死的预测全部正确**，在此基础上，JYY 希望为小镇上的每个居民 $k$ **分别计算有多少个火星人有可能和他一起活到第** $T+1$ 时刻，换言之，JYY 希望为每个火星人 $k$ 计算
$$\sum_{1\le i\le n,i\neq k} \text{Live}(k,i)$$
其中 $\text{Live}(i, j) = 1$ 表示编号为 $i$ 和 $j$ 的火星人有可能同时在第 $T + 1$ 时刻处于生还状态，否则 $\text{Live}(i, j) = 0$。
注意火星人是不能够复活的。一个火星人可能在时刻 $1$ 就处于死亡状态，也有可能有**预测未覆盖的死亡**情况发生（火星人在任何时候都可能死亡，但任意时刻观察到火星人的状态要么活着，要么死亡）。最后，注意到 $\text{Live}$ 是为每一对火星人**分别独立计算的**，因此 $\text{Live}(x, y) = \text{Live}(y, z) = 1$ 并不意味着 $\text{Live}(x, z) = 1$。
输入格式
输入第一行包含三个整数 $T, n, m$。
接下来有 $m$ 行，每行表示一条预言，每条预言第一个整数 $c$ 表示预言的类型：
- $c = 0$：接下来读入 $t, x, y$；
- $c = 1$：接下来读入 $t, x, y$。
接下来有 $m$ 行，每行表示一条预言，每条预言第一个整数 $c$ 表示预言的类型：
- $c = 0$：接下来读入 $t, x, y$；
- $c = 1$：接下来读入 $t, x, y$。
输出格式
输出 $n$ 个数表示答案，用空格分割。
输入输出样例
输入 #1
3 3 2 0 2 1 3 1 1 2 3
输出 #1
2 1 1
说明/提示
|测试点|$T$|$n$|$m$|
|:-:|:-:|:-:|:-:|
|$1$|$\le 2$|<!-- qwq -->$\le 10$|$\le 10$|
|$2,3$|<!-- quq -->$\le 100$|$\le 100$|$\le 200$|
|$4$|$\le 10^6$|$\le 3\times 10^3$|$\le 6\times 10^3$|
|$5,6$|$\le 4\times 10^4$|$\le 10^4$|$\le 2\times 10^4$|
|$7$|$\le 10^6$|$\le 3\times 10^4$|$\le 6\times 10^4$|
|$8$|$\le 10^6$|$\le 4\times 10^4$|$\le 8\times 10^4$|
|$9,10$|$\le 10^6$|$\le 5\times 10^4$|$\le 10^5$|
输入数据保证 $1 \le t \le T,1 \le x, y \le n$。
#### 提示
本题内存限制 1024MiB 包含进程中运行库、堆栈等所有内存，请特别留意。
|:-:|:-:|:-:|:-:|
|$1$|$\le 2$|<!-- qwq -->$\le 10$|$\le 10$|
|$2,3$|<!-- quq -->$\le 100$|$\le 100$|$\le 200$|
|$4$|$\le 10^6$|$\le 3\times 10^3$|$\le 6\times 10^3$|
|$5,6$|$\le 4\times 10^4$|$\le 10^4$|$\le 2\times 10^4$|
|$7$|$\le 10^6$|$\le 3\times 10^4$|$\le 6\times 10^4$|
|$8$|$\le 10^6$|$\le 4\times 10^4$|$\le 8\times 10^4$|
|$9,10$|$\le 10^6$|$\le 5\times 10^4$|$\le 10^5$|
输入数据保证 $1 \le t \le T,1 \le x, y \le n$。
#### 提示
本题内存限制 1024MiB 包含进程中运行库、堆栈等所有内存，请特别留意。