题解：AT_abc411_d [ABC411D] Conflict 2

IcyDragon · 2025-06-22 09:49:34 · 题解

思路

一看题以为 ABC 放水，写好暴力一交，结果……

再看一下题目，题目只保证了每次操作 2 的字符串不超过 10^6，而操作 1、3 直接复制的时空复杂度不能接受。

于是我们就需要用指针或一些奇奇怪怪的方法。

我们把每个 PC 和服务器的字符串用链表储存（分成一段一段连起来）。

每次操作 1、3，我们只需要把对应的指针复制过来，而不需要复制整个字符串，而对于操作 2，只需要在对应 PC 的链表后面插入这个字符串就行了。

因为一些奇怪的原因为了更容易实现，我们的链表是反着存的。

最后我们从服务器的链表头开始，遍历服务器的链表，把字符串放在一个临时数组里，把这个数组翻转过来，再挨个输出就是答案。

代码

AC 记录

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct Node{
    Node* nxt;
    string s;
};
Node* a[200100];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q,o,p;
    string s;
    Node* t;
    cin>>n>>q;
    a[0] = nullptr;
    while(q--){
        cin>>o>>p;
        if(o == 1){
            a[p] = a[0];
        }
        else if(o == 2){
            cin>>s;
            t = new Node{a[p],s};
            a[p] = t;
        }
        else{
            a[0] = a[p];
        }
    }
    vector<string> v;
    Node* pt = a[0];
    while(pt != nullptr){
        v.push_back(pt->s);
        pt = pt->nxt;
    }
    reverse(v.begin(),v.end());
    for(string s : v){
        cout<<s;
    }
    return 0;
}