题目详情题解（0）讨论（0）提交记录（0）

AT_abc411_d.[ABC411D] Conflict 2

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你有一台 服务器 和 NN 台 个人电脑（PC）。服务器和每台 PC 各自都持有一个字符串，初始时，这些字符串均为空串（""）。

接下来你会收到 QQ 个操作（查询），每个操作是以下三种类型之一：

  • 1 p：将 PC pp 的字符串 用服务器的字符串替换。
  • 2 p s：在 PC pp 的字符串 末尾追加字符串 ss。
  • 3 p：将服务器的字符串 用 PC pp 的字符串替换。

请你依照操作顺序处理完所有操作，输出最终的服务器字符串。

输入格式

第一行输入两个整数 NN 和 QQ。

接下来的 QQ 行：每行一个查询，格式如上所述。

输出格式

输出服务器的最终字符串。

输入输出样例

  • 输入#1

    2 6
2 1 at
3 1
2 2 on
1 2
2 2 coder
3 2

    输出#1

    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
说明/提示
限制条件


    

  • 1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5
    • 

  • 所有 p 的值都满足 1≤p≤N1 \le p \le N
    • 

  • 所有追加的字符串 ss 由小写字母组成，且长度之和不超过 10610^6
    • 



样例 1 解释


    

  1. 初始状态：服务器、PC1、PC2 的字符串都是 ""
    2. 

  2. 2 1 at：PC1 变为 "at"
    3. 

  3. 3 1：服务器变为 "at"
    4. 

  4. 2 2 on：PC2 变为 "on"
    5. 

  5. 1 2：PC2 被服务器 "at" 替换，变为 "at"
    6. 

  6. 2 2 coder：PC2 追加 "coder"，变为 "atcoder"
    7. 

  7. 3 2：服务器变为 "atcoder"
    8. 



最终服务器字符串为：atcoder


由 ChatGPT 4o 辅助翻译。


输入解题思路，AI测评打分。不知道怎么写? 
首页