題意#
此為「收集數字（Collecting Numbers）」進階版。
初始條件相同：給定 1 到 \( n \) 的排列陣列，由左至右遞增收集數字，計算所需回合數。
在此基礎上增加 \( m \) 次「交換操作」，每次操作會將指定兩個位置的數字互換。
需要求出：在「每次」交換結束後，總陣列皆需要花費幾回合方能收齊。
思路#
若每次交換後皆重新線性掃描計算回合數，時間複雜度達 \(\mathcal{O}(N \times M)\)，將導致 TLE。
需觀察交換操作的局部影響性質以達成 \(\mathcal{O}(1)\) 的狀態轉移。
交換位置 \( a \) 與 \( b \) 的數字 \( v[a] \) 和 \( v[b] \) 時，其位置的變動只會影響與其「數值相鄰」的相對位置。
也就是說，對回合數會產生增減影響的對象僅包含：\( v[a]-1 \)、\( v[a]+1 \)、\( v[b]-1 \)、\( v[b]+1 \) 及其本身。
因此可透過以下步驟 \(\mathcal{O}(1)\) 更新總回合數：
- 盤點受影響數對：將可能因交換而改變貢獻值的相鄰數對列出，共包含 \(\{v[a]-1, v[a]\}\), \(\{v[a], v[a]+1\}\), \(\{v[b]-1, v[b]\}\), \(\{v[b], v[b]+1\}\)。為避免兩數字相差一造成重複計算，使用
std::set過濾去重。 - 扣除交換前的貢獻：在尚未交換前，先確認這些數對是否對目前的總回合數有貢獻（也就是滿足前數值大於後數值的位置關係）。若有，將其從回合數中扣減。
- 執行交換：將陣列內位置 \( a \) 與 \( b \) 之元素互換，並同步更新
pos陣列中的位置資訊。 - 加回交換後的貢獻：在交換完成的新狀態下，重新檢視上列數對的貢獻情形，若滿足新貢獻，則在總回合加回一。
每次操作僅處理最多四組相鄰數對的貢獻，總時間複雜度降為 \(\mathcal{O}(N + M)\)。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// v[第幾個位置] = 原始的數字數值
// pos[數字數值 (0-based)] = 第幾個位置
signed main() { WA();
int n, m; cin >> n >> m;
vector<int> v(n), pos(n);
// 讀入陣列，並將數字數值減 1 轉成 0-based 以對應 pos 陣列
for (auto &i : v) cin >> i, pos[--i] = &i-v.data();
int cnt = 1;
// 預先計算未交換前的初始總回合數
for (int i = 0; i+1 < n; i++) if (pos[i+1] < pos[i]) cnt++;
while (m--) {
int a, b; cin >> a >> b;
// 將輸入的 1-based 位置轉為 0-based
a--, b--;
// st 儲存受交換影響的相鄰數對 {小值, 大值}
// 利用 set 過濾重複的數對
set<PII> st = {
{v[a]-1, v[a]}, {v[a], v[a]+1},
{v[b]-1, v[b]}, {v[b], v[b]+1}
};
// 交換前，判定數對的合法位置後，若具貢獻則予以扣減
for (auto &[x, y] : st)
if (x >= 0 && x < n && y >= 0 && y < n && pos[y] < pos[x])
cnt--;
// 正式交換彼此所在的記錄位置
swap(pos[v[a]], pos[v[b]]);
// 正式交換陣列裡面的數字
swap(v[a], v[b]);
// 交換後，針對新位置重新評估這些數對的貢獻並加回
for (auto &[x, y] : st)
if (x >= 0 && x < n && y >= 0 && y < n && pos[y] < pos[x])
cnt++;
// 即時印出當下被這兩個數字影響完後的最新總回合數
cout << cnt << '\n';
}
}
