Collecting Numbers II

You are given an array that contains each number between 1..n exactly once. Your task is to collect the numbers from 1 to n in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible.

Given m$m$ operations that swap two numbers in the array, your task is to report the number of rounds after each operation.

Example:

Input:  n = 5, q = 3, arr = {4, 2, 1, 5, 3}, queries = {{2, 3}, {1, 5}, {2, 3}}

Output:

2
3
4

Approach:

C++

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

void collectingNumbersII(int n, int q, vector<int> &arr,
                         vector<vector<int>> &queries)
{
    vector<int> pos(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        a[i] = arr[i - 1];
        pos[a[i]] = i;
    }
    int ans = 0;
    vector<bool> used(n + 1);
    for (int i = 1; i <= n; i++)
    {
        ans += !used[a[i] - 1];
        used[a[i]] = true;
    }
    for (int k = 0; k < q; k++)
    {
        int i = queries[k][0], j = queries[k][1];

        if (i > j)
            swap(i, j);
        int x = a[i], y = a[j];
        if (x + 1 <= n && i < pos[x + 1] && pos[x + 1] < j)
            ans++;
        if (x - 1 >= 1 && i < pos[x - 1] && pos[x - 1] < j)
            ans--;
        if (y + 1 <= n && i < pos[y + 1] && pos[y + 1] < j)
            ans--;
        if (y - 1 >= 1 && i < pos[y - 1] && pos[y - 1] < j)
            ans++;
        if (x + 1 == y)
            ans++;
        if (x - 1 == y)
            ans--;
        swap(a[i], a[j]);
        swap(pos[a[i]], pos[a[j]]);
        cout << ans << "\n";
    }
}

int main()
{

    int n = 5, q = 3;

    vector<int> arr = {4, 2, 1, 5, 3};

    vector<vector<int>> queries = {{2, 3}, {1, 5}, {2, 3}};

    collectingNumbersII(n, q, arr, queries);

    return 0;
}