solve the question in C++

Intuition

Because every A[i] is either 1, 2, or 3, the sorted array is

text
[ 1 … 1 ][ 2 … 2 ][ 3 … 3 ]
   cnt1      cnt2      cnt3

where

• cnt1 = number of 1’s in A
• cnt2 = number of 2’s in A
• cnt3 = number of 3’s in A (cnt3 = N-cnt1-cnt2)

If we know, for each value, how many of its elements sit in the three segments above, we can form the 3 × 3 “confusion” matrix

text
               segment that should contain →
value ↓        1-zone   2-zone   3-zone
        ---------------------------------
   1         M[1][1]  M[1][2]  M[1][3]
   2         M[2][1]  M[2][2]  M[2][3]
   3         M[3][1]  M[3][2]  M[3][3]

Only the off-diagonal cells matter.
Direct swaps:

text
x12 = min(M[1][2], M[2][1])   // fixes a 1↔2 pair
x13 = min(M[1][3], M[3][1])   // fixes a 1↔3 pair
x23 = min(M[2][3], M[3][2])   // fixes a 2↔3 pair
pairSwaps = x12 + x13 + x23

After those swaps, any remaining mis-placements form length-3 cycles (1→2→3→1).
Each such cycle costs 2 extra swaps, so

text
leftover   = totalMisplaced - 2*pairSwaps
tripleSwaps = 2 * (leftover / 3)
answer      = pairSwaps + tripleSwaps

Making it fast for up to 2 × 10⁵ updates

• We build three Fenwick/BIT trees, one per value (1, 2, 3).
  • add(val, idx, +1/-1) updates a single position in O(log N).
  • sum(val, r) gives “how many val in A[0..r]” in O(log N).
• A query A[p] = v does:
  1. Update the BITs at position p (remove the old value, add the new one).
  2. Read global counts cnt1, cnt2 in O(log N).
  3. With nine range-queries (one for each cell of M), fill the confusion matrix.
  4. Compute the formula above and append the result.

Per query we perform ≈ 9 log N operations – easily fast enough.

Reference implementation (C++17)

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n = 0) : n(n), bit(n + 1, 0) {}
    void add(int idx, int delta) {          // 1-based index inside BIT
        for (++idx; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    int sumPrefix(int idx) const {          // sum of [0 .. idx] (0-based)
        int res = 0;
        for (++idx; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    int sumRange(int l, int r) const {      // inclusive
        if (l > r) return 0;
        return sumPrefix(r) - (l ? sumPrefix(l - 1) : 0);
    }
};

vector<long long> Solve(int N, const vector<int>& Ainit,
                        int Q, const vector<array<int,2>>& queries)
{
    // 3 separate BITs, one per value (1,2,3). index 0..N-1
    vector<BIT> bits(4, BIT(N));            // use indices 1..3
    vector<int> A = Ainit;

    for (int i = 0; i < N; ++i)
        bits[A[i]].add(i, 1);

    vector<long long> answers;
    answers.reserve(Q);

    auto countVal = [&](int val, int l, int r) {
        return bits[val].sumRange(l, r);
    };

    for (const auto& qu : queries) {
        int pos = qu[0];
        int newVal = qu[1];

        if (A[pos] != newVal) {             // update BITs
            bits[A[pos]].add(pos, -1);
            bits[newVal].add(pos, +1);
            A[pos] = newVal;
        }

        // global counts
        int cnt1 = bits[1].sumPrefix(N - 1);
        int cnt2 = bits[2].sumPrefix(N - 1);
        int cnt3 = N - cnt1 - cnt2;

        int s1L = 0,          s1R = cnt1 - 1;
        int s2L = cnt1,       s2R = cnt1 + cnt2 - 1;
        int s3L = cnt1 + cnt2, s3R = N - 1;

        long long M[4][4] = {};            // only 1..3 used

        for (int v = 1; v <= 3; ++v) {
            M[v][1] = countVal(v, s1L, s1R);
            M[v][2] = countVal(v, s2L, s2R);
            M[v][3] = countVal(v, s3L, s3R);
        }

        long long x12 = min(M[1][2], M[2][1]);
        long long x13 = min(M[1][3], M[3][1]);
        long long x23 = min(M[2][3], M[3][2]);
        long long pairSwaps = x12 + x13 + x23;

        long long mis =
            (M[1][2] + M[1][3] + M[2][1] + M[2][3] + M[3][1] + M[3][2]);
        long long leftover = mis - 2 * pairSwaps;
        long long tripleSwaps = 2 * (leftover / 3);

        answers.push_back(pairSwaps + tripleSwaps);
    }
    return answers;
}

/* ---------------- driver -----------------
   The online judge usually provides the
   multiple-test-case wrapper like:

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<int> A(N);
        for (int& x: A) cin >> x;
        int Q; cin >> Q;
        vector<array<int,2>> qs(Q);
        for (auto& q: qs) cin >> q[0] >> q[1];
        auto out = Solve(N, A, Q, qs);
        for (long long x: out) cout << x << '\n';
    }
}
------------------------------------------ */

Complexities
Pre-processing – O(N log N) to build the BITs.
Per query – nine BIT range queries + two point updates ⇒ O(log N).
Memory – 3 · (N + 1) ints ≈ O(N).