题解：AT_abc411_d [ABC411D] Conflict 2

· · 题解

题解：AT_abc411_d [ABC411D] Conflict 2

题目传送门

题意

现在你有 N 台机器与一个服务器，服务器与 N 台机器都有一个字符串，最开始为空字符串。现有 Q 个查询，每个查询格式为：

1 p：把机器 p 的字符串改成服务器字符串。

2 p s：把机器 p 的字符串末尾加上字符串 s。

3 p：把服务器字符串改成机器 p 的字符串。

最后请输出服务器中的字符串。

思路

前置知识：crope

你如果正常模拟每次改变你会发现最后是会 TLE 和 MLE 和 RE 的，原因可能是内存超限了。所以我们可以用 crope 来模拟每次的加入和替换。从而不会让字符串的内存超限，它的原理是运用块状链表来实现的。

code

#include<bits/stdc++.h>
#include <ext/rope>//在c++11后可以使用
using namespace std;
using namespace __gnu_cxx;//必须要开这个，但我也不知道为什么。
crope a[250000];//此时我把服务器放置在a[0]的位置
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=0;i<q;i++){
        int t,p;
        string c;
        cin>>t;
        if(t==1){
            cin>>p;
            a[p].erase(0,a[p].size()-1);//删除a[p]中的所有字符
            a[p].replace(0,a[0]);//从第0位插入字符串a[0]
        }
        if(t==2){
            cin>>p>>c;
            for(int i=0;i<c.size();i++){
                a[p].push_back(c[i]);
            }//往a[p]后面依次插入字符
        }
        if(t==3){
            cin>>p;
            a[0].erase(0,a[0].size()-1);
            a[0].replace(0,a[p]);
        }
    }
    for(int i=0;i<a[0].size();i++){
        cout<<a[0][i];
    }//按照一位一位的输出答案
    return 0;
}