問題の内容を簡略化すると、以下のようになります。

\(N\) 個の要素からなる集合があり、\(i\) 個目の要素は \((S_i,i)\) である。以下のクエリを \(Q\) 個順に処理したあとの各要素を出力せよ。

• \(N\) 個の要素を \(S_i\) の昇順 → \(i\) の昇順、という優先順位で並べたとき、\(X_i\) 番目に来る要素が \((x,y)\) であるとする。集合から \((x,y)\) を削除し、代わりに \((T_i,y)\) を挿入する。

よってこの問題の本質は、以下の \(3\) つの処理をそれぞれ高速に行うこととなります。

• 集合に含まれる要素を適当な順序で並べたとき、\(k\) 番目に来る要素を求める。
• 集合から要素を削除する。
• 集合に要素を挿入する。

このような処理は、平衡二分探索木と呼ばれるデータ構造を用いることでそれぞれ \(O(\log N)\) で行うことが可能です。

C++ の場合、g++ 拡張の pb_ds (policy based data structure) を利用すると便利です。

実装例 (C++, Tester解)

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

template <class T>
using binary_search_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    fast_io();

    int n, q;
    cin >> n >> q;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    vector<int> x(q);
    vector<string> t(q);
    for (int i = 0; i < q; ++i) {
        cin >> x[i] >> t[i];
    }

    vector<string> c;
    c.reserve(s.size() + t.size());
    copy(begin(s), end(s), back_inserter(c));
    copy(begin(t), end(t), back_inserter(c));
    sort(begin(c), end(c));
    c.erase(unique(begin(c), end(c)), end(c));
    vector<int> s_id(n);
    for (int i = 0; i < n; ++i) {
        s_id[i] = distance(begin(c), lower_bound(begin(c), end(c), s[i]));
    }
    vector<int> t_id(q);
    for (int i = 0; i < q; ++i) {
        t_id[i] = distance(begin(c), lower_bound(begin(c), end(c), t[i]));
    }

    binary_search_tree<pair<int, int>> set;
    for (int i = 0; i < n; ++i) {
        set.insert({s_id[i], i});
    }
    for (int i = 0; i < q; ++i) {
        auto itr = set.find_by_order(x[i] - 1);
        int k = itr->second;
        s_id[k] = t_id[i];
        set.erase(itr);
        set.insert({s_id[k], k});
    }

    for (int i = 0; i < n; ++i) {
        cout << c[s_id[i]] << " \n"[i + 1 == n];
    }

    return 0;
}

なお、Trie 木を用いることで各処理を（\(σ=26\) として）\(O(σ)\) で行い、この問題に AC することも可能です。

実装例 (C++, Writer解)

#include<bits/stdc++.h>
using namespace std;

// trie
struct trie{
    int maxi;
    vector<int> node;
    vector<vector<int>> next;
    trie(int el_sz): maxi(el_sz){
        node.resize(1);
        next.emplace_back(vector<int>(maxi, -1));
    }
    void insert(vector<int> A){
        int now = 0;
        for(auto el: A){
            if(next[now][el] == -1){
                next[now][el] = node.size();
                node.emplace_back(0);
                next.emplace_back(vector<int>(maxi,-1));
            }
            now = next[now][el];
            node[now]++;
        }
    }
    // 1-indexed
    vector<int> kth_element(int k){
        int now = 0;
        vector<int> ret;
        while(true){
            bool flag = false;
            for(int i=0; i<maxi; i++){
                if(next[now][i] == -1) continue;
                if(k <= node[next[now][i]]){
                    flag = true;
                    ret.emplace_back(i);
                    now = next[now][i];
                    break;
                }
                else k -= node[next[now][i]];
            }
            if(!flag) break;
        }
        return ret;
    }
    void erase(vector<int> A){
        int now = 0;
        for(auto el: A){
            now = next[now][el];
            node[now]--;
        }
    }
};

vector<int> translate(string S, int idx){
    vector<int> ret;
    for(auto el: S) ret.emplace_back(el-'a'+10);
    string idx_ = to_string(idx);
    for(int i=idx_.size(); i<5; i++) ret.emplace_back(0);
    for(auto el: idx_) ret.emplace_back(el-'0');
    return ret;
}

pair<string,int> inverse(vector<int> A){
    string S = "";
    int idx = 0;
    for(auto el: A){
        if(10 <= el) S += 'a'+el-10;
        else idx = idx*10+el;
    }
    return make_pair(S,idx);
}

int main(){
    int N,Q; cin >> N >> Q;
    vector<string> S(N);
    for(int i=0; i<N; i++) cin >> S[i];
    trie tr(36);
    for(int i=0; i<N; i++) tr.insert(translate(S[i],i));
    while(Q--){
        int X; cin >> X;
        string T; cin >> T;
        auto A = tr.kth_element(X);
        auto p = inverse(A);
        tr.erase(A);
        tr.insert(translate(T,p.second));
    }
    vector<string> ans(N);
    for(int i=0; i<N; i++){
        auto A = tr.kth_element(1);
        auto p = inverse(A);
        tr.erase(A);
        ans[p.second] = p.first;
    }
    cout << ans[0];
    for(int i=1; i<N; i++) cout << " " << ans[i];
    cout << "\n";
}