Exchange Queries

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

static inline ll sq(ll x) { return x * x; }

struct SqrtGaps {
    struct Group {
        int val, first, last;
        ll inside;
    };

    int n, m, B, nb, W;
    vector<int> cnt, bel, L, R, lazy;
    vector<int16_t> where;
    vector<vector<Group>> groups;

    SqrtGaps() {}

    SqrtGaps(int n_, const vector<int>& a) {
        init(n_, a);
    }

    int getId(int b, int v) const {
        return where[(size_t)b * W + v];
    }

    void setId(int b, int v, int id) {
        where[(size_t)b * W + v] = (int16_t)id;
    }

    void init(int n_, const vector<int>& a) {
        n = n_;
        m = n - 1;
        B = 320;
        nb = (m + B - 1) / B;
        W = n + 1;

        cnt.assign(m + 1, 0);
        vector<int> diff(m + 2, 0);
        for (int i = 1; i <= n; i++) {
            int l = min(i, a[i]);
            int r = max(i, a[i]) - 1;
            if (l <= r) {
                diff[l]++;
                diff[r + 1]--;
            }
        }
        for (int i = 1, cur = 0; i <= m; i++) {
            cur += diff[i];
            cnt[i] = cur;
        }

        bel.assign(m + 1, 0);
        L.resize(nb);
        R.resize(nb);
        lazy.assign(nb, 0);
        groups.assign(nb, {});
        where.assign((size_t)nb * W, (int16_t)-1);

        for (int b = 0; b < nb; b++) {
            L[b] = b * B + 1;
            R[b] = min(m, (b + 1) * B);
            for (int i = L[b]; i <= R[b]; i++) bel[i] = b;
            rebuild(b);
        }
    }

    void materialize(int b) {
        if (lazy[b] == 0) return;
        for (int i = L[b]; i <= R[b]; i++) cnt[i] += lazy[b];
        lazy[b] = 0;
    }

    void rebuild(int b) {
        for (auto &g : groups[b]) setId(b, g.val, -1);
        groups[b].clear();

        for (int i = L[b]; i <= R[b]; i++) {
            int v = cnt[i];
            int id = getId(b, v);
            if (id == -1) {
                id = (int)groups[b].size();
                setId(b, v, id);
                groups[b].push_back({v, i, i, 0});
            } else {
                Group &g = groups[b][id];
                g.inside += sq(i - g.last);
                g.last = i;
            }
        }
    }

    void rangeAdd(int l, int r, int delta) {
        if (l > r || m == 0) return;
        int bl = bel[l], br = bel[r];
        if (bl == br) {
            materialize(bl);
            for (int i = l; i <= r; i++) cnt[i] += delta;
            rebuild(bl);
            return;
        }

        materialize(bl);
        for (int i = l; i <= R[bl]; i++) cnt[i] += delta;
        rebuild(bl);

        materialize(br);
        for (int i = L[br]; i <= r; i++) cnt[i] += delta;
        rebuild(br);

        for (int b = bl + 1; b < br; b++) lazy[b] += delta;
    }

    void addInterval(int x, int y, int delta) {
        if (x == y) return;
        if (x > y) swap(x, y);
        rangeAdd(x, y - 1, delta);
    }

    ll sumSquares() const {
        ll ans = 0;
        int prev = 0;

        for (int b = 0; b < nb; b++) {
            int need = -lazy[b];
            if (need < 0 || need > n) continue;
            int id = getId(b, need);
            if (id == -1) continue;

            const Group &g = groups[b][id];
            ans += sq(g.first - prev) + g.inside;
            prev = g.last;
        }

        ans += sq(n - prev);
        return ans;
    }
};

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;

        vector<int> p(n + 1), s(n + 1), a(n + 1);
        for (int i = 1; i <= n; i++) cin >> p[i];
        for (int i = 1; i <= n; i++) cin >> s[i];
        for (int i = 1; i <= n; i++) a[p[i]] = s[i];

        SqrtGaps ds(n, a);

        while (q--) {
            int tp, i, j;
            cin >> tp >> i >> j;

            int x = p[i], y = p[j];
            int ax = a[x], ay = a[y];

            ds.addInterval(x, ax, -1);
            ds.addInterval(y, ay, -1);
            ds.addInterval(x, ay, +1);
            ds.addInterval(y, ax, +1);
            swap(a[x], a[y]);

            if (tp == 1) swap(p[i], p[j]);
            else swap(s[i], s[j]);

            ll sccSquares = ds.sumSquares();
            cout << (sq(n) + sccSquares) / 2 << '\n';
        }
    }

    return 0;
}