Giải bài toán copy ~2~ dãy ~B~ và ~C~:

Với mỗi truy vấn copy, ta tính lại mảng ~D(i)~ là truy vấn cuối cùng mà ta copy dãy ~B~ sang dãy ~C~, ảnh hưởng đến vị trí ~i~ của ~C~. Thay vì duyệt ~i~ từ ~y~ đến ~y + k - 1~ và gán thì ta có thể dùng CTDL Segment Tree để gán nhanh.

Nếu ~D(i) = 0~ (chưa được gán) thì ~C(i)~ không đổi. Ngược lại ~C(i) = B(x + i - y)~. Với ~x~ và ~y~ thuộc truy vấn thứ ~D(i)~.

Ở bài toán gốc, mảng ~D(i)~ không giúp ta không truy vết được giá trị cụ thể của ~B~ copy sang ~C~. Nhưng ta lại truy vết được giá trị của ~B~ copy sang ~C~ là ~B(x + i - y)~ và tại thời điểm ~D(i)~. Nhờ thông tin đó, bài toán của ta trở thành tìm giá trị của một số vị trí trong ~B~, tại một số thời điểm.

Làm lại quá trình trên một lần nữa nhưng với hai dãy ~A~ và ~B~. Sau đó tại mỗi thời điểm cần quan tâm, ta sẽ biết được giá trị một số vị trí của ~B~ là bao nhiêu.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
template <typename A, typename B> bool maximize(A& a, B b) {
    return a < b ? a = b, true : false;
}
template <typename A, typename B> bool minimize(A& a, B b) {
    return a > b ? a = b, true : false;
}

struct Segtree {
    int n;
    vector<int> t;

    Segtree(int _n) {
        n = _n;
        t.resize(4 * n + 1, 0);
    }

    void push(int v) {
        if (t[v]) {
            t[v << 1] = t[v << 1 | 1] = t[v];
            t[v] = 0;
        }
    }

    void update(int node, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            t[node] = val;
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        update(node << 1, l, mid, u, v, val);
        update(node << 1 | 1, mid + 1, r, u, v, val);
    }

    int get(int node, int l, int r, int pos) {
        if (l > pos || r < pos) return 0;
        if (l == r) return t[node];
        push(node);
        int mid = (l + r) >> 1;
        return get(node << 1, l, mid, pos) + get(node << 1 | 1, mid + 1, r, pos);
    }
};

const int N = 5e5 + 5;

int n, q;
int a[N], b[N], c[N];
int t[N], x[N], y[N], k[N];
vector<pair<int, int>> queries[N];
int ans[N];

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++ i) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; ++ i) {
        cin >> c[i];
    }
    Segtree sgt(n);
    for (int i = 1; i <= q; ++ i) {
        cin >> t[i];
        if (t[i] == 1) {
            cin >> x[i] >> y[i] >> k[i];
        }
        if (t[i] == 2) {
            cin >> x[i] >> y[i] >> k[i];
            sgt.update(1, 1, n, y[i], y[i] + k[i] - 1, i);
        } 
        if (t[i] == 3) {
            cin >> x[i];
            auto time = sgt.get(1, 1, n, x[i]);
            if (time == 0) {
                ans[i] = c[x[i]];
            } else {
                queries[time].push_back({x[time] + x[i] - y[time], i});
            }
        }
    }
    sgt = Segtree(n);
    for (int i = 1; i <= q; ++ i) {
        if (t[i] == 1) {
            sgt.update(1, 1, n, y[i], y[i] + k[i] - 1, i);
        }
        for (auto [pos, id] : queries[i]) {
            int spos = sgt.get(1, 1, n, pos);
            if (spos == 0) ans[id] = b[pos];
            else ans[id] = a[x[spos] + pos - y[spos]];
        }
    }
    for (int i = 1; i <= q; ++ i) {
        if (ans[i]) cout << ans[i] << "\n";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
#endif
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}