分数: 425 点
问题陈述
有一台服务器,并且 N 电脑。 服务器和每台PC各持有一个字符串,最初所有字符串都是空的。 给出了
Q 查询。每个查询均采用以下格式之一:
1 p: 替换PC的字符串 p 与服务器的字符串。2 p s:追加字符串 s 到PC字符串的末尾 p.3 p:将服务器的字符串替换为PC的字符串 p.
按给定顺序处理所有查询后查找服务器的最终字符串。
约束
- N,Q 是整数
- 1\leq N,Q \leq 2\times 10^5
- 对于每个查询, p 是一个整数并且 1 \leq p\leq N.
- 对于每个类型的查询 2, s 是长度至少为 1 由小写英文字母组成。
- 的长度总和 s 类型的所有查询 2 最多是 10^6.
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 代表 i-th 查询,并以下列格式之一给出:
1 p
2 p s
3 p
输出
输出答案。
示例输入 1
2 6 2 1 at 3 1 2 2 on 1 2 2 2 coder 3 2
示例输出 1
atcoder
- 最初,服务器和PC的字符串 1,2 全部为空。
- 1st 查询:追加
at到PC字符串的末尾 1。此时服务器、PC的字符串 1,2 为空,at,分别为空。 - 2nd查询:将服务器的字符串替换为PC的字符串 1。此时服务器、PC的字符串 1,2 是
at,at,分别为空。 - 3rd 查询:追加
on到PC字符串的末尾 2。此时服务器、PC的字符串 1,2 是at,at,on。 - 4第查询:替换PC的字符串 2 与服务器的字符串。此时服务器、PC的字符串 1,2 是
at,at,at。 - 5第查询:追加
coder到PC字符串的末尾 2。此时服务器、PC的字符串 1,2 是at,at,atcoder。 - 6th 查询:将服务器的字符串替换为 PC 的字符串 2。此时服务器、PC的字符串 1,2 是
atcoder,at,atcoder。
因此,服务器的最终字符串是 atcoder.
示例输入 2
100000 3 1 100 2 300 abc 3 200
示例输出 2
服务器的最终字符串为空。 正整数(可能为空)的
示例输入 3
10 10 2 7 ladxf 2 7 zz 2 7 kfm 3 7 1 5 2 5 irur 3 5 1 6 2 6 ptilun 3 6
示例输出 3
ladxfzzkfmirurptilun