solve the question in C++
Created on: July 5, 2025
Created on: July 5, 2025
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
textsegment 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:
textx12 = 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
textleftover = totalMisplaced - 2*pairSwaps tripleSwaps = 2 * (leftover / 3) answer = pairSwaps + tripleSwaps
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[p] = v
does:
p
(remove the old value, add the new one).cnt1, cnt2
in O(log N)
.Per query we perform ≈ 9 log N operations – easily fast enough.
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).