solve the question in C++

Created on: July 5, 2025

Answered using O3 by Chat01

Question

b34d056e-2d2c-487e-b706-33a728d7ac90.jpgb34d056e-2d2c-487e-b706-33a728d7ac90.jpg
02253dfe-ba42-4737-b76b-045371d9d081.jpg02253dfe-ba42-4737-b76b-045371d9d081.jpg
ab70cd2d-25f4-4619-a0ee-7653cf89e55e.jpgab70cd2d-25f4-4619-a0ee-7653cf89e55e.jpg
f82951fc-9eff-42ad-bc78-2aca7ff5e466.jpgf82951fc-9eff-42ad-bc78-2aca7ff5e466.jpg

solve the question in C++

Thought

Analyzing the problem

The user's question involves sorting an array with values 1, 2, and 3, given specific update queries. Each query updates an element in the array, and we need to find the minimum number of swaps to sort the array after each update.

The problem description involves determining how to implement this efficiently in C++ while considering multiple test cases. I'll need to structure the solution carefully, ensuring the number of swaps is calculated accurately after each update.

Optimizing swap counting logic

To solve this, I need to efficiently calculate the minimal number of swaps required to sort an array of values {1, 2, 3}, updating after each query. The approach involves computing a confusion matrix to track misplacements, enabling efficient swap calculation by counting misplaced elements. Each query alters one element, which affects segment counts and the confusion matrix. The goal is to minimize swaps by counting direct swaps and cycles of length 3, updating these values dynamically for each query. Precomputing prefix counts will help speed up this process.

Thought for 18 seconds

Answer

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).

Share this Q&A