#P12359. [eJOI 2024] 古迹漫步 / Old Orhei
[eJOI 2024] 古迹漫步 / Old Orhei
题目描述
在摩尔多瓦的鲁特河旁有一个著名古建筑群。这个古建筑群由 个古建筑和 条单向道路组成。每条道路根据输入顺序都有一个编号,从前到后分别编号为 。
最近,科学家发现了一个由 Cucuteni 文化留下的数列!这个数列由 个 的数组成。为了寻找这个数列的神秘意义,新来的实习生被要求执行以下操作:
最开始,实习生在某个古建筑处。其他科学家则开始将神秘数列的子序列一一念给他。假设当前实习生在第 个古建筑,科学家念出的数为 ,那么:
-
如果第 条道路的起点恰好是 ,那么实习生沿着这条道路走到相连的古建筑。
-
否则,实习生站在原地不动。
正值第 界 EJOI 的举行,当地的科学家希望你能帮助他们解决如下 个问题:
-
1 L R S
:科学家想知道,如果最开始实习生站在第 个古建筑处,然后他们将神秘数列中第 项念给他,那么实习生最终在哪个古建筑停下。 -
2 i K
:科学家们将神秘数列的第 项的值修改为 。
你需要对于所有问题 1
,给出正确的回答!
输入格式
第一行,两个正整数 ;
接下来 行,第 行两个整数 ,表示第 条道路的起点和终点;
接下来一行一个正整数 ;
接下来一行 个整数 ,表示神秘序列。
接下来一行一个正整数 ;
接下来 行,每行一个问题。格式见题目描述。
输出格式
对于所有问题 1
输出答案,每行一个。
5 6
1 2
3 2
4 2
2 5
5 1
4 5
6
2 1 4 2 5 3
3
1 3 5 2
1 3 5 2
1 1 2 3
1
1
2
3 3
1 2
2 3
3 1
4
3 1 1 2
4
1 1 2 3
2 2 2
1 1 2 3
1 1 4 2
2
1
3
2 3
1 1
1 2
1 2
4
1 1 2 3
3
1 1 2 1
2 1 2
1 1 2 1
1
2
提示
【数据范围】
本题采用 捆绑测试。
分值 | 特殊性质 | |
---|---|---|
,且唯一一个问题是问题 1 |
||
保证没有问题 2 ,且 |
||
无 |
对于 的数据,$1 \le N \le 50,1 \le M,T,Q\le 10^5,1\le X_i,Y_i\le N,1 \le A_i \le M,1 \le L \le R \le T,1 \le S \le N,1 \le i \le T,1\le K\le M$。