题解：AT_abc411_d [ABC411D] Conflict 2

GYHL · 2025-06-22 19:57:54 · 题解

题目传送门

题目大意

有一台服务器和 n 台个人电脑。服务器和每台个人电脑各有一个字符串，最初所有字符串都是空的。

给出了 q 个查询，每个查询都是以下格式之一：

• 1 p：用服务器的字符串替换个人电脑 p 的字符串。
• 2 p s：在个人电脑 p 的字符串的末尾添加字符串 s。
• 3 p:用个人电脑 p 的字符串替换服务器的字符串。

按照给定的顺序处理所有查询后，找出服务器的最终字符串。

思路

直接模拟会超时，因为字符串的赋值操作是 \mathcal{O}(N) 的。

所以考虑通过建有向图的方式来维护题目的操作。为了方便，将服务器设置为 0 号个人电脑。

• 对于操作 1、3：修改该字符串上的结点的实际编号即可。
• 对于操作 2：用 0 号个人电脑到结点的路径来表示字符串的拼接操作。

做法

• 对于操作 1：将个人电脑的结点的实际编号指向服务器结点（不创建新节点）。
• 对于操作 2：
  1. 创建新的结点，用来存储追加的字符串。
  2. 其父节点指向个人电脑的结点，并跟新当前结点。
• 对于操作 3：将服务器结点指向个人电脑的结点的实际编号（不创建新节点）。

详细见代码。

代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N = 2e5 + 10;
int a[N], fa[N];
string s[N];

void dfs(int x) {
    if (!x) return;
    dfs(fa[x]);
    cout << s[x];
}

/*
维护一个图，用边来表示操作
a[x] -> 第x个字符串，对应哪个点
fa[num] -> 第num个点，是由哪个点转移过来的
s[num] -> 从 fa[num] 到 num  新增了哪个字符串
nw -> 根节点实际上是哪个点
*/

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, num = 0, nw = 0;
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1)
            a[x] = nw;
        else if (op == 2) {
            num++;
            cin >> s[num];
            fa[num] = a[x];
            a[x] = num;
        } else
            nw = a[x];
    }
    dfs(nw);
    return 0;
}