暴力枚举

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
pair<int, int> e[100000 + 5];
int t, a[100000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].first >> e[i].second;
    cin >> t;
    for (int i = 1; i <= t; i++)
        cin >> a[i];
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, s;
            cin >> l >> r >> s;
            for (int i = l; i <= r; i++)
            {
                int id = a[i];
                if (s == e[id].first)
                    s = e[id].second;
            }
            cout << s << "\n";
        }
        else
        {
            int i, k;
            cin >> i >> k;
            a[i] = k;
        }
    }

    return 0;
}

满分的分块

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int siz;
string temp;
string e[100000 + 5];
int t, a[100000 + 5];
// ee[i]: [(i-1)*siz,i*siz) 的合成
string ee[1000 + 5];
void con(string &a, string &b)
{
    for (int i = 0; i <= n - 1; i++)
        a[i] = b[a[i]];
}
void cal(int id)
{
    int l = id * siz;
    int r = min(l + siz - 1, t - 1);
    ee[id] = e[a[l]];
    for (int i = l + 1; i <= r; i++)
        con(ee[id], e[a[i]]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    temp = "";
    for (int i = 0; i <= n - 1; i++)
        temp = temp + (char)i;
    for (int i = 0; i <= m - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[i] = temp;
        e[i][u] = v;
    }
    cin >> t;
    siz = sqrt(t);
    for (int i = 0; i <= t - 1; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    // 每 siz 个一合成
    for (int l = 0; l <= t - 1; l += siz)
        cal(l / siz);
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, s;
            cin >> l >> r >> s;
            l--, r--, s--;
            int i;
            for (i = l; i <= r && i % siz != 0; i++)
                s = e[a[i]][s];
            for (; i + siz <= r; i += siz)
                s = ee[i / siz][s];
            for (; i <= r; i++)
                s = e[a[i]][s];
            cout << s + 1 << "\n";
        }
        else
        {
            int i, k;
            cin >> i >> k;
            i--, k--;
            a[i] = k;
            cal(i / siz);
        }
    }

    return 0;
}