题解：AT_abc411_d [ABC411D] Conflict 2

P2441M · 2025-06-22 10:52:41 · 题解

题意

有 n+1 个字符串，依次标号为 0,1,\cdots,n。进行 q 次操作：

• 1 p：令 s_p\leftarrow s_0。
• 2 p s：令 s_p\leftarrow s_p+s，其中 + 表示字符串拼接。
• 3 p：令 s_0\leftarrow s_p。

执行完所有操作后，求 s_0。1\leq n,q\leq 2\times 10^5，0\leq\sum|s|\leq 10^6。

题解

招笑做法。

显然不能暴力模拟，那么考虑使用链表。具体地，在链表节点上记录前驱 prv 和当前节点对应的字符串 s，用 tail_i 记录 s_i 的尾部节点。那么操作 1,3 就直接赋值，操作 2 往 tail_p 后添加一个新节点即可。最后取出 tail_0 处的链表复原即可。时间复杂度 \mathcal{O}(q+\sum|s|)。

代码

#include <iostream>
#include <string>

using namespace std;

#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;

int n, q;
int top;
string stk[N];

int tot;
struct Node {
    int prv;
    string s;
} nodes[N];
int tail[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    while (q--) {
        int op, p; cin >> op >> p;
        string str;
        if (op == 1) tail[p] = tail[0];
        else if (op == 2) {
            cin >> str;
            nodes[++tot] = {tail[p], str};
            tail[p] = tot;
        } else tail[0] = tail[p];
    }
    for (int p = tail[0]; p; p = nodes[p].prv) stk[++top] = nodes[p].s;
    for (int i = top; i; --i) cout << stk[i];
    return 0;
}