CSES – Collecting Numbers II

題目連結

題意

給一個 n 跟 1 ~ n 的 permutation。每次你可以從左往右拿數字，但是你拿到數字必須要是遞增的。有 m 次操作，每次操作會把兩個數字位子互相調換。每次操作完後，輸出最少可以花幾次就拿完全部的數字。

解題想法

跟上一題是一樣的思路，只是要處理 swap 數字他們的大小關係會怎麼改變。
細節請看 code
註：注意out of bounds error, 這題用 1-based 會比較好做

#include <bits/stdc++.h>
using namespace std;
int main(){    
    int n, q;
    cin >> n >> q;
    vector <int> a(n+1), idx(n+2);
    idx[0] = 0, idx[n+1] = n+1; // 方便實作
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        idx[a[i]] = i;
    }
    int cnt = 1;
    for(int i = 1;i <= n;i++){
        if(idx[i] <= idx[i-1])
            cnt++;
    }

    while(q--){
        int l, r; 
        cin >> l >> r;
        int x = a[l], y = a[r];
        swap(a[l], a[r]); // 判斷交換時候要怎麼改變答案
        if (idx[x-1] <= idx[x] && idx[x-1] > r) cnt++;
        if (idx[x-1] > idx[x] && idx[x-1] <= r) cnt--;
        if (idx[x] <= idx[x+1] && r > idx[x+1]) cnt++;
        if (idx[x] > idx[x+1] && r <= idx[x+1]) cnt--;		
        idx[x] = r;
        if (idx[y-1] <= idx[y] && idx[y-1] > l) cnt++;
        if (idx[y-1] > idx[y] && idx[y-1] <= l) cnt--;
        if (idx[y] <= idx[y+1] && l > idx[y+1]) cnt++;
        if (idx[y] > idx[y+1] && l <= idx[y+1]) cnt--;	
        idx[y] = l;

        cout << cnt << '\n';
    }
}