それぞれの操作を \(O(1+\min\lbrace l _ i,l _ {s _ i}\rbrace\log N)\) 時間で処理するためには、平衡二分探索木や連結リストを用いるのがよいです。

例えば、std::set を用いて \(\bigl\lbrace(i,A _ i)\bigr\rbrace\) と \(\bigl\lbrace(A _ i,i)\bigr\rbrace\) をそれぞれ管理することで、それぞれのクエリを十分高速に処理することができます。

実装例は以下のようになります。 以下の実装例では、\(\bigl\lbrace(A _ i,i)\bigr\rbrace\) を管理する平衡二分探索木を \(2\) つに分けることで \(x _ i\) と中央値との大小関係がすぐにわかるようにしています（このようにしなくても、両端から進んで先に「 \(x\) より大」の境界線をまたぐのはどちらか判定することで十分高速になります）。

#include <set>
#include <utility>
#include <iterator>
#include <iostream>
#include <vector>
#include <ranges>


// 列を管理するクラス
// 以下の操作を O(log N) 時間で行う。
//  - 先頭・末尾の削除
//  - 最小・最大要素の削除
//  - 先頭・末尾への追加
//  - 最小・最大要素の値の取得
//  - 中央値の取得
//
// (より正確には、組 (i, v) の集合について i の最小・最大および v の最小・最大・中央値を管理するクラス)
class sequence {
  public:
    using value_type = std::pair<unsigned, unsigned>;
    std::set<value_type> original, small, large;

    // 中央値を計算できるように大小の set の大きさを揃える
    void balance() {
        while (std::size(small) > std::size(large)) {
            large.emplace_hint(std::begin(large), *std::prev(std::end(small)));
            small.erase(std::prev(std::end(small)));
        }
        while (std::size(small) + 1 < std::size(large)) {
            small.emplace_hint(std::end(small), *std::begin(large));
            large.erase(std::begin(large));
        }
    }

    value_type pop_helper(unsigned i, unsigned v) {
        original.erase(std::make_pair(i, v));
        small.erase(std::make_pair(v, i));
        large.erase(std::make_pair(v, i));
        balance();
        return {i, v};
    }

public:
    void swap(sequence &rhs) {
        using std::swap;
        swap(original, rhs.original);
        swap(small, rhs.small);
        swap(large, rhs.large);
    }

    sequence() = default;

    auto min() const {
        return std::begin(std::empty(small) ? large : small)->first;
    }

    auto mid() const {
        return std::begin(large)->first;
    }

    auto max() const {
        return std::prev(std::end(large))->first;
    }

    void emplace(unsigned long i, unsigned long v) {
        original.emplace(i, v);
        (v < mid() ? small : large).emplace(v, i);
        balance();
    }

    void emplace(const value_type &value) {
        emplace(value.first, value.second);
    }

    auto empty() const noexcept {
        return std::empty(original);
    }

    auto size() const noexcept {
        return std::size(original);
    }

    auto pop_front() {
        const auto[i, v]{*begin(original)};
        return pop_helper(i, v);
    }

    auto pop_back() {
        const auto[i, v]{*std::prev(std::end(original))};
        return pop_helper(i, v);

    }

    auto pop_min() {
        const auto[v, i]{*std::begin(std::empty(small) ? large : small)};
        return pop_helper(i, v);
    }

    auto pop_max() {
        const auto[v, i]{*std::prev(std::end(large))};
        return pop_helper(i, v);
    }
};

int main() {
    using namespace std;
    unsigned N;
    cin >> N;

    vector<sequence> sequences(1);
    for (unsigned a; const auto i : views::iota(0U, N)) {
        cin >> a;
        sequences.front().emplace(i, a); // i 番目の要素 A[i] を追加する
    }

    unsigned Q;
    cin >> Q;
    sequences.resize(1 + Q);
    for (unsigned t, s, x; const auto i : views::iota(1U, 1 + Q)) {
        cin >> t >> s >> x;
        if (t == 1) { // x 個目より後を移動
            const auto M{size(sequences[s])};
            if (2 * x < M) { // 移動しない要素のほうが少ないとき
                swap(sequences[s], sequences[i]); // 入れ替えて
                for (const auto _ : views::iota(0U, x)) // x 個目以前を
                    sequences[s].emplace(sequences[i].pop_front()); // 前から順に移動
            } else if (x < M)
                for (const auto _ : views::iota(x, M)) // x 個目より後を
                    sequences[i].emplace(sequences[s].pop_back()); // 後ろから順に移動
        } else { // x より大きな要素を移動
            if (x < sequences[s].mid()) { // x が中央値より小さいとき
                swap(sequences[s], sequences[i]); // 入れ替えて
                while (!empty(sequences[i]) && sequences[i].min() <= x) // x 以下の要素が残っている限り
                    sequences[s].emplace(sequences[i].pop_min()); // 小さいほうから順に移動
            } else
                while (!empty(sequences[s]) && sequences[s].max() > x) // x より大きい要素が残っている限り
                    sequences[i].emplace(sequences[s].pop_max()); // 大きいほうから順に移動
        }
        cout << size(sequences[i]) << endl; // i 番の数列の大きさを出力
    }
    return 0;
}