徐老师的羊腿生产
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师的羊腿工厂中有 $n$ 台机器可以生产羊腿，每台机器前面都有一个存储箱来存放生产好的羊腿。
而徐老师编制了一份长度为 $k$ 的生产方案，方案中，每个单位时间执行下面三个操作之一：
- `+ i`：让第 $i$ 台机器生产一个羊腿，并放在它所属的存储箱中；
- `E i`：清空第 $i$ 台机器所属的存储箱，把这些羊腿送到徐老师家里；
- `S i j`：将第 $i$ 台机器的存储箱中的羊腿和第 $j$ 台中的羊腿交换（保证 $i\neq j$）。
这 $n$ 台机器不断循环执行这份生产方案
现在徐老师想知道第 $i$ 台机器在重复了 $m_i$ 轮生产方案后，它所属的存储箱中有多少个羊腿。
输入格式
第一行两个正整数 $n,k\ (1\le n,k\le 10^6)$。
接下来 $k$ 行，表示这套方案中的每一个操作，保证 $1\le i,j\le n,i\neq j$。
接下来一行 $n$ 个整数 $m_1,m_2,\ldots,m_n\ (1\le m_i\le 10^9)$，第 $i$ 个整数表示徐老师想知道第 $i$ 台机器在重复了 $m_i$ 轮生产方案后，它所属的存储箱中有多少个羊腿。
本题共 $20$ 组数据。
对于 $15\%$ 的数据，$n,k\le 100$。
对于另 $15\%$ 的数据，$k\le 10^5,m_i\le 100$。
对于另 $30\%$ 的数据，$n\le 10^5$。
对于全部数据，$1\le n,k\le 10^6,1\le m_i\le 10^9,1\le i,j\le n,i\neq j$。
输出格式
输出一行包含 $n$ 个整数，表示每次询问的答案
样例
5 3
+ 1
S 1 4
E 1
1 2 3 4 50 0 0 1 02023暑CSP-S复赛集训模拟赛四
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-31 22:15
- 结束于
- 2023-8-10 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 20
