Find and Replace (USACO Gold 2023 January Gold)

此题写起来比较简单的解法是在on-demand的二叉树上做DFS，如果不用二叉树，或者不用DFS，都会写起来比较繁琐。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
ll l,r;
int n;
vector<pair<char,string>> ops;
const ll INF = 1e18;
 
struct Node {       // binary tree for each operation
    char c;
    ll size;
    Node *l, *r;
    void print(ll st, ll en) {
        ll left = l ? l->size : 0;
        if (l && st < left)
            l->print(st, min(en, left));
        if (c != ' ') cout << c;
        if (r && en > left)
            r->print(max(0ll, st - left), en - left);
    }
};
Node *cur[26];
 
int main() {
    ios :: sync_with_stdio(false);
    cin >> l >> r >> n;
    ops.resize(n);
    for (int i = 0; i < n; i++)
        cin >> ops[i].first >> ops[i].second;
 
    for (char c = 'a'; c <= 'z'; c++)
        cur[c-'a'] = new Node{c, 1};
    for (int i = n-1; i >= 0; i--) {    // build tree from bottom up
        Node *res = nullptr;
        for (char c: ops[i].second) {
            Node *tgt = cur[c-'a'];
            res = res ?  
                    new Node{' ', min(INF, res->size + tgt->size), res, tgt}
                  : tgt;
        }
        cur[ops[i].first-'a'] = res;
    }
    cur[0]->print(l-1, r);
    return 0;
}